Union-Find leagă nodurile, nu rădăcinile: ciclurile nu sunt detectate
La reuniune ai scris parinte[a] = b, care rupe nodul a din grupul lui vechi. Trebuie să legi rădăcinile: ra, rb = gaseste(a), gaseste(b); dacă sunt diferite, parinte[ra] = rb. Altfel grupurile se despart și găsirea ciclurilor dă rezultate greșite.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Structura Union-Find (Disjoint Set Union) ține fiecare grup ca un arbore: fiecare nod indică spre părinte, iar rădăcina reprezintă grupul. gaseste(x) urcă până la rădăcină, iar uneste(a, b) face ca rădăcina unui grup să indice spre rădăcina celuilalt.
Dacă scrii parinte[a] = b, muți doar nodul a, iar legătura lui veche dispare. Nodurile care depindeau de a rămân cu el, dar alte noduri din grupul vechi rămân separate. Grupurile se rup pe nesimțite, iar gaseste(a) == gaseste(b) răspunde „nu sunt conectate” pentru noduri care chiar sunt.
Nu primești nicio eroare. Simptomele: ciclurile (muchia redundantă) nu sunt găsite, numărul de componente iese prea mare, rezultatele diferă după ordinea muchiilor.
De ce apare: cauzele frecvente
1Reuniune pe noduri
def uneste(a, b):
parinte[a] = bdef uneste(a, b):
ra, rb = gaseste(a), gaseste(b)
if ra != rb:
parinte[ra] = rbRădăcina reprezintă tot grupul; legând rădăcinile, toate nodurile ambelor grupuri ajung în același arbore.
2Comparare fără gaseste()
if parinte[a] == parinte[b]:
return (a, b)if gaseste(a) == gaseste(b):
return (a, b)Părintele direct nu e neapărat rădăcina. Două noduri din același grup pot avea părinți diferiți.
3gaseste fără compresie, pe lanțuri lungi
def gaseste(x):
while parinte[x] != x:
x = parinte[x]
return xdef gaseste(x):
if parinte[x] != x:
parinte[x] = gaseste(parinte[x])
return parinte[x]Prima variantă e corectă, dar lentă pe lanțuri lungi. Compresia drumului leagă direct fiecare nod de rădăcină.
Repară eroarea, direct în pagină
Funcția cablu_in_plus(n, cabluri) returnează primul cablu de rețea care închide o buclă, folosind Union-Find. Testul cu assert pică: buclă nu e detectată, pentru că reuniunea leagă nodurile, nu rădăcinile. Repar-o ca să afișeze (2, 3).
def cablu_in_plus(n, cabluri):
parinte = list(range(n + 1))
def gaseste(x):
while parinte[x] != x:
x = parinte[x]
return x
def uneste(a, b):
parinte[a] = b
for a, b in cabluri:
if gaseste(a) == gaseste(b):
return (a, b)
uneste(a, b)
return None
rez = cablu_in_plus(3, [(1, 2), (1, 3), (2, 3)])
assert rez == (2, 3), f'bucla negasita: {rez}'
print(rez)(2, 3)
Indiciu
În uneste, găsește întâi rădăcinile lui a și b și leagă rădăcina de rădăcină.
Reparația
def cablu_in_plus(n, cabluri):
parinte = list(range(n + 1))
def gaseste(x):
while parinte[x] != x:
x = parinte[x]
return x
def uneste(a, b):
ra, rb = gaseste(a), gaseste(b)
if ra != rb:
parinte[ra] = rb
for a, b in cabluri:
if gaseste(a) == gaseste(b):
return (a, b)
uneste(a, b)
return None
rez = cablu_in_plus(3, [(1, 2), (1, 3), (2, 3)])
assert rez == (2, 3), f'bucla negasita: {rez}'
print(rez)De ce merge
După cablul (1, 2), nodul 1 indica spre 2. La (1, 3), parinte[1] = 3 a mutat nodul 1 spre 3 și l-a rupt de 2, deci 2 a rămas singur și cablul (2, 3) nu mai părea o buclă. Legând rădăcinile, grupul {1, 2} se unește întreg cu 3, iar la (2, 3) ambele noduri au aceeași rădăcină.
Cum o eviți pe viitor
Scrie uneste mereu în trei pași: găsește rădăcinile, compară-le, leagă rădăcinile. Pentru viteză adaugă compresia drumului în gaseste și, opțional, reuniunea după mărime. Testează cu muchii care unesc grupuri deja formate, de exemplu (1, 2), (1, 3), (2, 3), unde ultima muchie închide un ciclu.
Întrebări frecvente
Cât de rapid e Union-Find?
Cu compresia drumului și reuniune după mărime, fiecare operație e aproape O(1) în practică.
Merge pe grafuri orientate?
Union-Find răspunde doar la „sunt în același grup?”, deci se potrivește grafurilor neorientate. Pentru cicluri în grafuri orientate folosește DFS cu stări sau sortarea topologică.
Erori înrudite
Sortarea topologică nu detectează ciclul: returnează o ordine incompletă Algoritmul lui Kahn scoate doar nodurile fără dependențe rămase; nodurile dintr-un ciclu nu ajung niciodată la gradul 0, deci lipsesc din rezultat. La final verifică len(ordine) == n și returnează None (sau o eroare) dacă nu e așa. RecursionError la DFS: graful are un ciclu și lipsesc nodurile vizitate DFS-ul recursiv nu ține minte nodurile vizitate, iar graful are un ciclu (sau e neorientat: A-B înseamnă și B-A), deci se plimbă la nesfârșit până la RecursionError. Adaugă un set vazut și nu reintra în nodurile din el. Graful neorientat are muchiile adăugate doar într-un sens: BFS nu ajunge la toate nodurile Pentru un graf neorientat (drumuri, prietenii, cabluri), fiecare muchie u-v trebuie adăugată în ambele liste: graf[u].append(v) și graf[v].append(u). Cu un singur sens, din v nu mai poți ajunge înapoi la u, iar BFS/DFS ratează noduri. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
