3338 - disjoint

Cerinţa

Răspundeți la toate întrebările de al doilea tip, în ordinea acestora.

Date de intrare

Programul citește de la tastatură numerele N și M, iar apoi M triplete de numere naturale de forma op x y, unde op poate lua doar valorile 1 și 2, aceste triplete reprezentând câte o operație.

Date de ieşire

Programul va afișa pe ecran, pe câte o linie, răspunsul la fiecare întrebare de tip 2. Dacă la întrebarea 2 x y răspunsul este afirmativ, adică x și y se află în aceeași clasă, atunci veți afișa DA, iar în caz contrar veți afișa NU.

Restricții și precizări

• 1 ≤ N ≤ 500
• 2 ≤ M ≤ 2000
• va exista cel puțin o operație de tip 1 și cel puțin o operație de tip 2.

Exemplu

Intrare

6 6

1 1 4

1 3 6

2 4 6

1 1 3

2 4 6

2 1 6

Ieșire

NU

DA

DA

Explicație

Sunt 6 copii și 6 operații. După primele două operații, elevii 1 și 4 sunt în aceeași clasă și 3 și 6 sunt în aceeași clasă. La întrebarea 2 4 6 răspunsul este evident NU. La a patra operație 1 și 3 sunt trecuți în aceeași clasă, deci va exista o clasă cu 4 copii: {1,3,4,6}, deci la ultimele două întrebări acum răspunsul este DA la ambele.

Rezolvare

# Funcția 'find' returnează reprezentantul (sau liderul) al setului în care se află un element dat.
def find(parent, i):
    if parent[i] == i:
        return i
    return find(parent, parent[i])

# Funcția 'union' este utilizată pentru a uni două seturi.
def union(parent, rank, x, y):
    xroot = find(parent, x)
    yroot = find(parent, y)

    # Atașează arborele mai mic la rădăcina celui mai mare
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else :
        parent[yroot] = xroot
        rank[xroot] += 1

# Funcția 'solve' citește datele de intrare și rezolvă problema.
def solve():
    N, M = map(int,input().strip().split())
    parent = [i for i in range(N+1)]
    rank = [0 for _ in range(N+1)]
    res = []
    
    for _ in range(M):
        op, x, y = map(int,input().strip().split())
        if op == 1:
            union(parent, rank, x, y)
        else:
            # Dacă x și y au același părinte (adică sunt în aceeași clasă), atunci afișează 'DA'
            if find(parent, x) == find(parent, y):
                res.append('DA')
            else:
                res.append('NU')
    
    print('\n'.join(res))

# Acest cod va fi executat doar dacă scriptul este rulat direct
if __name__ == "__main__":
    solve()