Union-Find: mulțimi disjuncte
O rețea de calculatoare primește, pe rând, cabluri noi între aparate. După fiecare cablu vrei să știi imediat: sunt aparatele X și Y legate? Câte rețele separate sunt acum? Ai putea rula un DFS de fiecare dată, dar Union-Find (mulțimi disjuncte) răspunde în timp aproape constant, chiar dacă legăturile vin una câte una.
Ideea: fiecare grup are un șef
Fiecare element arată spre un părinte; urmând părinții ajungi la rădăcina grupului (șeful lui). Două elemente sunt în același grup dacă au același șef. Două operații:
parinte = list(range(6)) # la început, fiecare element este propriul șef
def gaseste(x):
while parinte[x] != x:
x = parinte[x] Completează clasa UnionFind (gaseste cu comprimarea drumului, uneste după rang, care întoarce False dacă elementele erau deja în același grup). Apoi scrie muchia_redundanta(muchii), care returnează prima muchie ce închide un ciclu (nodurile…
- gaseste: dacă parinte[x] != x, parinte[x] = gaseste(parinte[x]); întorci parinte[x].
- uneste: găsești rădăcinile; dacă sunt egale, False; altfel legi rădăcina cu rang mai mic sub cealaltă și întorci True.
- muchia_redundanta: prima muchie pentru care uneste întoarce False. numar_componente: pornești de la n și scazi 1 la fiecare unire reușită.
- Trebuie să apară: [2, 3], [1, 4], [], 2, 4, 1.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan