Ce este o structură disjoint-set (union-find) cu compresie de cale și uniune după rang?

Question

Accepted Answer

Un **disjoint-set** (union-find) urmărește elementele partiționând în grupuri care nu se suprapun și răspunde la "**sunt aceste două în același grup?**" și "**îmbină două grupuri**" în **timp aproape constant**. Cu **compresie de cale** și **uniune după rang**, ambele operații rulează în **O(α(n))** — practic O(1) (α este funcția inversă Ackermann).

## Cum funcționează

Fiecare set este un arbore; **rădăcina** este reprezentantul setului. `find` merge la rădăcină; `union` leagă o rădăcină sub alta.

```text
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
   before:  a->b->c->root      after:  a->root, b->root, c->root
```

## Cod

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # halve path
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True
```

| Operație | Timp (cu ambele optimizări) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Utilizări comune

- **MST al lui Kruskal** — îmbină componente fără a forma cicluri.
- **Componente conectate** într-un graf sau grilă.
- **Conectivitate dinamică** și probleme de rețea/percolație.

## De ce contează

Union-find rezolvă probleme de grupare și conectivitate care ar necesita altfel parcurgeri de graf repetate O(n), comprălindule la aproape O(1) per interogare.

Este un instrument incontournable ori de câte ori trebuie să îmbinezi treptat seturi și să testezi conectivitatea — subiect frecvent la interviuri de nivel senior.