3338 - disjoint: Difference between revisions

From Bitnami MediaWiki
No edit summary
 
Line 1: Line 1:
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:
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>
<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ă
* 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>
<br>
* 2 x y – întrebare: copiii cu numerele x și y sunt sau nu în aceeași clasă?
* 2 x y – întrebare: copiii cu numerele x și y sunt sau nu în aceeași clasă?

Latest revision as of 14:19, 9 December 2023

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[edit | edit source]

Răspundeți la toate întrebările de al doilea tip, în ordinea acestora.

Date de intrare[edit | edit source]

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[edit | edit source]

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[edit | edit source]

  • 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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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