Introdução
Você foi contratado para desenvolver o Noble Knots, o mais badalado aplicativo de relacionamentos para a nobreza!
Com séculos de casamentos entre a realeza, as coisas ficaram… complicadas.
Para evitar qualquer situação do tipo opa, somos gêmeos, sua tarefa é construir um sistema que verifica o quão próximo é o parentesco entre duas pessoas.
O Noble Knots foi inspirado no "Islendinga-App" da Islândia, que tem por trás um banco de dados que traça todas as conexões familiares conhecidas entre islandeses desde o povoamento da Islândia.
Seu algoritmo vai determinar o grau de separação entre duas pessoas na árvore genealógica da realeza.
Será que seu aplicativo vai ajudar a coroar o par perfeito?
Instruções
Sua tarefa é determinar o grau de separação entre duas pessoas em uma árvore genealógica.
Isso é parecido com a ideia da cultura pop de que todo ator de Hollywood está a seis graus de Kevin Bacon.
- Você vai receber uma entrada com todos os nomes dos pais e seus filhos.
- Cada nome é único, e uma criança pode ter um ou dois pais.
- O grau de separação é definido como o menor número de conexões de uma pessoa até outra.
- Se duas pessoas não estiverem conectadas, retorne um valor que represente "no known relationship."
Veja os casos de teste para saber a implementação real.
Exemplo
Dada a seguinte árvore genealógica:
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
O grau de separação entre Tariq e Uma é 2 (Tariq → Isla → Uma).
Não há relação conhecida entre Isla e Kevin, já que não existe conexão nos dados fornecidos.
O grau de separação entre Uma e Isla é 1.
Isla e Tariq são irmãos e têm uma separação de 1.
Da mesma forma, esta implementação reportaria uma separação de 2 entre você e o irmão do seu pai.
