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:

• 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ă

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

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

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

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