Ce este union-find și unde se folosește?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) urmărește o partiție de elemente în **mulțimi disjuncte** și suportă două operații aproape-O(1): **find** (în care mulțime se află x?) și **union** (îmbină două mulțimi). Excelează la interogări de **conectivitate**.

## Ideea

Fiecare mulțime este un arbore cu o rădăcină reprezentativă. Cu **compresie de cale** și **uniune după rang/mărime**, operațiile rulează în timp **amortizat** aproape constant (inversul Ackermann, α(n)).

## Exemplu

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # compress
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already connected
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra           # attach smaller under larger
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
```

## Complexitate

- **find / union:** O(α(n)) ≈ O(1) amortizat. **Spațiu:** O(n).

## Aplicații

- **MST Kruskal** — detecția ciclurilor în timp ce adaugă muchii.
- **Componente conexe** / conectivitate dinamică.
- **Detecția ciclurilor** în grafuri neorientate.
- **Percolație**, segmentare de imagini, fuzionare de conturi/rețele.

## Capcane

Fără compresie de cale și uniune după rang, arborii se degradează la lanțuri O(n). Nu suportă *scindare* eficientă a mulțimilor.

## De ce contează

Union-find răspunde la "sunt acestea două lucruri conectate?" la scară masivă cu aproape niciun cost.

Este motorul din spatele MST Kruskal și al multor algoritmi de grafuri și clustering.

Cele două optimizări ale sale sunt o lecție memorabilă despre cum trucuri structurale mici obțin performanță aproape constantă în timp.