Editing 3338 - disjoint

Se consideră N copii, numerotați de la 1 la N și fiecare face parte dintr-o clasă. Inițial sunt n clase și fiecare copil face parte din propria sa clasă. Se dau M operații de două tipuri:
<br>
* 1 x y – acțiune: clasele din care fac parte copiii cu numerele x și y se reunesc. Dacă x și y fac deja parte din aceeași clasă, operația nu se efectuează
<br>
* 2 x y – întrebare: copiii cu numerele x și y sunt sau nu în aceeași clasă?
== 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'''.
== Exemplul 1 ==
; Intrare
: 6 6
: 1 1 4
: 1 3 6
: 2 4 6
: 1 1 3
: 2 4 6
: 2 1 6
; Ieșire
: Datele introduse corespund restricțiilor impuse.
: NU
: DA
: DA
== Exemplul 2 ==
; Intrare
: 6 6
: 1 1 4
: 1 3 6
: 2 4 6
: 1 1 3
: 2 4 6
: 2 1 520
; Ieșire
: Datele introduse nu corespund restricțiilor impuse.
== 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>
# 3338 - disjoint
def validare(n, m, operati):
    # Verificăm dacă N și M sunt în limitele specificate și dacă avem numărul corect de operații
    if n < 1 or n > 500 or m < 2 or m > 2000 or len(operati) != m:
        raise ValueError
    tip1 = tip2 = False
    for op, x, y in operati:
        # Verificăm dacă există cel puțin o operație de fiecare tip
        if op == 1:
            tip1 = True
        elif op == 2:
            tip2 = True
        # Verificăm dacă operațiile sunt valide
        if op not in [1, 2] or x < 1 or x > n or y < 1 or y > n:
            raise ValueError
    # Verificăm dacă există cel puțin o operație de fiecare tip
    if not (tip1 and tip2):
        raise ValueError

    print("Datele de intrare corespund restrictiilor impuse")
    return True


# Funcția 'rezolvare' rezolvă problema dată
def rezolvare(n, _, operati):
    # Inițializăm părinții și rangurile
    parent = [i for i in range(n + 1)]
    rank = [0 for _ in range(n + 1)]
    res = []

    # Funcția 'find' găsește reprezentantul unui element
    def find(i):
        if parent[i] == i:
            return i
        return find(parent[i])

    # Funcția 'union' unește două seturi
    def union(x1, y2):
        xroot = find(x1)
        yroot = find(y2)

        # Atașăm 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

    # Parcurgem operațiile și le aplicăm
    for op, x, y in operati:
        if op == 1:
            union(x, y)
        else:
            # Dacă x și y au același părinte, atunci sunt în aceeași clasă
            if find(x) == find(y):
                res.append('DA')
            else:
                res.append('NU')

    # Afișăm rezultatele
    print('\n'.join(res))


# Acest cod va fi executat doar dacă scriptul este rulat direct
if __name__ == '__main__':
    try:
        # Citim datele de intrare
        N, M = map(int, input().strip().split())
        operatii = [list(map(int, input().strip().split())) for _ in range(M)]
        # Validăm datele de intrare
        validare(N, M, operatii)
        # Rezolvăm problema
        rezolvare(N, M, operatii)
    # Tratăm eventualele erori
    except ValueError:
        print("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>