Cos'è una struttura disjoint-set (union-find) con path compression e union by rank?

Question

IT Interview Practice · Accepted Answer

Una **disjoint-set** (union-find) tiene traccia di elementi partizionati in gruppi non sovrapposti e risponde a "**questi due sono nello stesso gruppo?**" e "**unisci due gruppi**" in **tempo quasi-costante**. Con **path compression** e **union by rank**, entrambe le operazioni eseguono in **O(α(n))** — effettivamente O(1) (α è la funzione inversa di Ackermann).

## Come funziona

Ogni insieme è un albero; la **radice** è il rappresentante dell'insieme. `find` cammina verso la radice; `union` collega una radice sotto un'altra.

```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
```

## Codice

```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
```

| Operazione | Tempo (con entrambe le ottimizzazioni) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Usi comuni

- **MST di Kruskal** — unisci componenti senza formare cicli.
- **Componenti connesse** in un grafo o griglia.
- **Connettività dinamica** e problemi di rete/percolazione.

## Perché è importante

Union-find risolve problemi di raggruppamento e connettività che altrimenti richiederebbero ripetuti attraversamenti di grafo O(n), riducendoli a quasi O(1) per query.

È uno strumento essenziale quando devi incrementalmente unire insiemi e testare connettività — un argomento frequente nei colloqui per livelli senior.

Come funziona

Codice

Usi comuni

Perché è importante

Domande correlate