O que é uma estrutura disjoint-set (union-find) com compressão de caminho e união por rank?

Question

Accepted Answer

Uma **disjoint-set** (union-find) rastreia elementos particionados em grupos não sobrepostos e responde a "**esses dois estão no mesmo grupo?**" e "**mesclar dois grupos**" em **tempo quase-constante**. Com **compressão de caminho** e **união por rank**, ambas as operações executam em **O(α(n))** — efetivamente O(1) (α é a função inversa de Ackermann).

## Como funciona

Cada conjunto é uma árvore; a **raiz** é o representante do conjunto. `find` caminha até a raiz; `union` vincula uma raiz sob a outra.

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

## Código

```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ção | Tempo (com ambas otimizações) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Usos comuns

- **MST de Kruskal** — mesclar componentes sem formar ciclos.
- **Componentes conectadas** em um grafo ou grade.
- **Conectividade dinâmica** e problemas de rede/percolação.

## Por que isso importa

Union-find resolve problemas de agrupamento e conectividade que de outra forma precisariam de traversais de grafo repetidas O(n), reduzindo-os para quase O(1) por consulta.

É uma ferramenta essencial sempre que você deve mesclar incrementalmente conjuntos e testar conectividade — um tópico frequente em entrevistas de nível sênior.