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>

1. 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])

1. 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

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

1. Acest cod va fi executat doar dacă scriptul este rulat direct

if __name__ == "__main__":

   solve()

</syntaxhighlight>