2458 - Hobby

Enunt

În școala lui Gigel copiii se pregătesc pentru vacanță. Ei vor să-și petreacă timpul liber în mod diferit în funcție de hobby-urile pe care le au. În concluzie, urmează să formeze grupuri, pe baza preferințelor. Totuși, a apărut o problemă. Unii sunt dispuși să renunțe la propriul hobby și preferă să facă parte dintr-un grup din care face parte și un anumit prieten al lor. În școala lui Gigel sunt n copii, numerotați de la 1 la n.

Cerinţa

Cunoscând prietenul preferat și hobby-ul fiecărui copil, scrieți un program care determină numărul grupurilor care se vor forma și numărul grupurilor formate din copii care au hobby-uri identice; doi copii vor face parte din același grup, dacă cel puțin unul din cei doi l-a numit pe celălalt ca prieten.

Date de intrare

Pe prima linie a fișierului de intrare hobby1.in se află un număr natural n, reprezentând numărul copiilor. Pe fiecare din următoarele n linii se află câte o pereche de numere naturale, unde primul număr reprezintă numărul de ordine al copilului având ca prieten preferat copilul identificat cu cel de al doilea număr. Pe următoarele n linii se află, pe fiecare, câte un șir de caractere format din litere mici ale alfabetului englez, reprezentând hobby-urile copiilor în ordinea în care sunt numerotați copiii.

Date de ieșire

Pe prima linie a fișierului de ieșire hobby1.out veți scrie numărul gr al grupurilor de copii. Pe următoarea linie veți afișa numărul grupurilor în care toți copiii au același hobby.

Restricţii şi precizări

• 1 ≤ n ≤ 700.
• 1 ≤ lungime_denumire_hobby ≤ 10.
• 1 ≤ gr ≤ 400.
• numărul de ordine al fiecărui copil apare o singură dată pe prima poziție a unei perechi.
• un copil poate fi prietenul mai multor copii.
• numărul maxim al hobby-urilor: 20.
• La concurs s-au dat 10 puncte din oficiu, aici sunt date pe exemplu.

Exemplu

hobby.in

8
1 2
3 4
5 6
7 7
8 3
2 1
4 3
6 2
baschet
baschet
tenis
fotbal
baschet
baschet
muzica
tenis

hobby.out

3
2

Explicație

Avem 3 grupuri: 1: 1 2 5 6 2: 7 3: 3 4 8 Toți copiii din primul grup (cu numerele de ordine 1 2 5 6) au ca hobby baschetul, copilul 7 este singur, iar în al treilea grup hobby-urile diferă. Deci avem 2 grupuri în care copiii au același hobby.

Rezolvare

def form_groups(n, preferences, hobbies):
    groups = {}  # Dicționar pentru a înregistra grupurile

    for i in range(1, n+1):
        friend = preferences[i]
        hobby = hobbies[i]

        # Verificăm dacă prietenul preferat este deja într-un grup
        if friend in groups:
            # Adăugăm copilul curent în grupul prietenului său
            groups[friend].append(i)
            groups[i] = groups[friend]  # Actualizăm grupul pentru copilul curent
        else:
            # Creăm un nou grup pentru ei
            groups[i] = [i]

    return groups

def count_same_hobbies(groups, hobbies):
    same_hobby_groups = 0

    for group in groups.values():
        # Verificăm dacă toți copiii din grup au același hobby
        same_hobby = all(hobbies[child] == hobbies[group[0]] for child in group)
        if same_hobby:
            same_hobby_groups += 1

    return same_hobby_groups

def main():
    with open("hobby.in", "r") as fin:
        n = int(fin.readline())
        preferences = {}
        hobbies = {}

        for _ in range(n):
            child, friend = map(int, fin.readline().split())
            preferences[child] = friend

        for _ in range(n):
            hobbies[i] = fin.readline().strip()

    # Formăm grupurile
    groups = form_groups(n, preferences, hobbies)

    # Numărăm grupurile cu aceleași hobby-uri
    same_hobby_groups = count_same_hobbies(groups, hobbies)

    # Scriem rezultatul în fișierul de ieșire
    with open("hobby.out", "w") as fout:
        fout.write(str(len(groups)) + "\n")
        fout.write(str(same_hobby_groups) + "\n")

if __name__ == "__main__":
    main()