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