Qu'est-ce qu'une structure disjointe (union-find) avec compression de chemin et union par rang ?

Question

Accepted Answer

Une **structure disjointe** (union-find) suit les éléments partitionnés en groupes non chevauchants et répond aux questions « **ces deux éléments sont-ils dans le même groupe ?** » et « **fusionner deux groupes** » en **temps quasi-constant**. Avec **compression de chemin** et **union par rang**, les deux opérations s'exécutent en **O(α(n))** — effectivement O(1) (α est la fonction inverse d'Ackermann).

## Fonctionnement

Chaque ensemble est un arbre ; la **racine** est le représentant de l'ensemble. `find` remonte jusqu'à la racine ; `union` lie une racine sous une autre.

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

## Code

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

| Opération | Temps (avec les deux optimisations) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Utilisations courantes

- **MST de Kruskal** — fusionner les composantes sans former de cycles.
- **Composantes connexes** dans un graphe ou une grille.
- **Connectivité dynamique** et problèmes de réseau/percolation.

## Pourquoi c'est important

Union-find résout les problèmes de regroupement et de connectivité qui nécessiteraient autrement des traversées de graphe O(n) répétées, en les réduisant à pratiquement O(1) par requête.

C'est un outil incontournable chaque fois que vous devez fusionner progressivement des ensembles et tester la connectivité — un sujet d'entretien fréquent au niveau senior.