Com abordar aquest problema

Se't donen relacions de parentiu del tipus X HIJO DE Y, i has de saber si dues persones formen part del mateix arbre familiar (encara que la relació sigui llunyana), no només si hi ha una relació directa entre elles.

Idea general:

1. Llegeix el nombre de casos de prova.
2. Per a cada cas, llegeix quantes línies té (relacions + la línia final amb el nom a consultar).
3. Per a cada relació X HIJO DE Y, afegeix una connexió (aresta) entre X i Y en una estructura de graf (per exemple, un diccionari on cada nom apunta a un conjunt dels noms amb qui està directament connectat).
4. Un cop construït el graf d'aquest cas, recorre'l a partir de THOR (amb una cerca en amplada o en profunditat, BFS/DFS) per trobar tots els noms que formen part del seu mateix arbre familiar.
5. Comprova si el nom que es demana és un d'aquests, i escriu SI o NO.
6. Recorda construir un graf nou per a cada cas de prova: les relacions no es mantenen d'un cas a l'altre.

Paranys habituals:

• Encara que la relació s'escrigui en una sola direcció (X HIJO DE Y), a efectes de "ser família" la connexió funciona en els dos sentits: si X és família d'Y, Y també ho és de X.
• No et quedis només mirant si hi ha una línia directa amb els dos noms: cal seguir la cadena de connexions (família llunyana).
• Vigila quantes línies de relacions llegeixes en cada cas (compte amb el desfàs entre M i M-1).