3338 - disjoint - Revision history

Hotico Iulia Denisa at 14:19, 9 December 2023

2023-12-09T14:19:43Z

← Older revision		Revision as of 14:19, 9 December 2023
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ă?

Hotico Iulia Denisa: /* Cerinţa */

2023-12-09T14:19:13Z

Cerinţa

← Older revision		Revision as of 14:19, 9 December 2023
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:
			<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 ==		== Cerinţa ==
	Răspundeți la toate întrebările de al doilea tip, în ordinea acestora.		Răspundeți la toate întrebările de al doilea tip, în ordinea acestora.

	== Date de intrare ==		== 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.		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.

Zmicala Narcis at 10:16, 14 November 2023

2023-11-14T10:16:33Z

Show changes

Zmicala Narcis: Pagină nouă: == 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 întrebar...

2023-10-31T08:23:14Z

Pagină nouă: == 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 întrebar...

New page

== 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>
# 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])

# 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

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

# Acest cod va fi executat doar dacă scriptul este rulat direct
if __name__ == "__main__":
solve()

</syntaxhighlight>