O que é union-find e onde é usado?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) rastreia uma partição de elementos em **conjuntos disjuntos** e suporta duas operações quase-O(1): **find** (em qual conjunto x está?) e **union** (mesclar dois conjuntos). É excelente em consultas de **conectividade**.

## A ideia

Cada conjunto é uma árvore com uma raiz representativa. Com **compressão de caminho** e **union por rank/tamanho**, operações rodam em tempo **amortizado** quase constante (Ackermann inverso, α(n)).

## Exemplo

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

## Complexidade

- **find / union:** O(α(n)) ≈ O(1) amortizado. **Espaço:** O(n).

## Aplicações

- **MST de Kruskal** — detecção de ciclos ao adicionar arestas.
- **Componentes conectadas** / conectividade dinâmica.
- **Detecção de ciclos** em grafos não direcionados.
- **Percolação**, segmentação de imagens, fusão de contas/redes.

## Armadilhas

Sem compressão de caminho e union por rank, árvores se degradam para cadeias O(n). Não suporta *divisão* eficiente de conjuntos.

## Por que isso importa

Union-find responde "essas duas coisas estão conectadas?" em escala massiva com quase nenhum custo.

É o motor dentro do MST de Kruskal e muitos algoritmos de grafos e clustering.

Suas duas otimizações são uma lição memorável de como pequenos truques estruturais geram desempenho quase constantemente rápido.