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.

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

# 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")