Editing 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 ==
<syntaxhighlight lang="python" line>
# 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()

</syntaxhighlight>