...
Eroare Algoritmi și structuri de date · Grafuri: BFS și DFS

Union-Find leagă nodurile, nu rădăcinile: ciclurile nu sunt detectate

Pe scurt

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

Greșit
PYTHON
def uneste(a, b):
    parinte[a] = b
Corect
PYTHON
def uneste(a, b):
    ra, rb = gaseste(a), gaseste(b)
    if ra != rb:
        parinte[ra] = rb

Rădăcina reprezintă tot grupul; legând rădăcinile, toate nodurile ambelor grupuri ajung în același arbore.

2Comparare fără gaseste()

Greșit
PYTHON
if parinte[a] == parinte[b]:
    return (a, b)
Corect
PYTHON
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

Greșit
PYTHON
def gaseste(x):
    while parinte[x] != x:
        x = parinte[x]
    return x
Corect
PYTHON
def 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ă tu

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

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
(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ă.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

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