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).

Pista per a Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int casos = Integer.parseInt(sc.nextLine().trim());

        for (int c = 0; c < casos; c++) {
            int m = Integer.parseInt(sc.nextLine().trim());
            Map<String, Set<String>> graf = new HashMap<>();

            for (int i = 0; i < m - 1; i++) {
                String[] parts = sc.nextLine().trim().split("\\s+");
                String x = parts[0];
                String y = parts[parts.length - 1]; // "X HIJO DE Y"
                graf.computeIfAbsent(x, k -> new HashSet<>()).add(y);
                graf.computeIfAbsent(y, k -> new HashSet<>()).add(x);
            }

            String consulta = sc.nextLine().trim();

            // BFS des de THOR
            Set<String> visitats = new HashSet<>();
            visitats.add("THOR");
            Deque<String> cua = new ArrayDeque<>();
            cua.add("THOR");
            while (!cua.isEmpty()) {
                String actual = cua.poll();
                for (String vei : graf.getOrDefault(actual, Collections.emptySet())) {
                    if (!visitats.contains(vei)) {
                        visitats.add(vei);
                        cua.add(vei);
                    }
                }
            }

            System.out.println(visitats.contains(consulta) ? "SI" : "NO");
        }
    }
}

El Map<String, Set<String>> graf es crea de nou a cada cas, dins del bucle principal.