Introdução
Foste contratado para desenvolver a Noble Knots, a nova aplicação de encontros mais badalada para a nobreza!
Com séculos de casamentos entre famílias reais, as coisas ficaram… complicadas.
Para evitar qualquer situação do tipo ups-somos-gémeos, a tua tarefa é construir um sistema que verifica o grau de parentesco entre duas pessoas.
A Noble Knots inspira-se na "Islendinga-App" islandesa, que é sustentada por uma base de dados que traça todas as ligações familiares conhecidas entre islandeses desde o povoamento da Islândia.
O teu algoritmo vai determinar o grau de separação entre duas pessoas na árvore genealógica da família real.
Será que a tua aplicação vai ajudar a coroar um par perfeito?
Instruções
A tua tarefa é determinar o grau de separação entre duas pessoas numa árvore genealógica.
Isto é semelhante à ideia da cultura popular de que qualquer ator de Hollywood está a menos de seis graus de Kevin Bacon.
- Recebes uma entrada com os nomes de todos os pais e os respetivos 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 ligações entre uma pessoa e outra.
- Se duas pessoas não estiverem ligadas, devolve um valor que represente "nenhuma relação conhecida".
Consulta os casos de teste para veres a implementação concreta.
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 existe nenhuma relação conhecida entre Isla e Kevin, uma vez que não há qualquer ligação nos dados fornecidos.
O grau de separação entre Uma e Isla é 1.
Isla e Tariq são irmãos e têm um grau de separação de 1.
Da mesma forma, esta implementação indicaria um grau de separação de 2 entre ti e o irmão do teu pai.
