Padrão 3: Union-Find (conjuntos disjuntos)

Como responder rapidamente "esses dois nós estão no mesmo grupo?" enquanto grupos vão se fundindo? O Union-Find (ou DSU — disjoint set union) faz exatamente isso: agrupar e consultar conexão em tempo quase constante.

🎯

Tente primeiro: Graph Valid Tree

Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.

Dados n nós e uma lista de edges não-dirigidas, retorne true se o grafo forma uma árvore válida (totalmente conectado e sem ciclos).

Exemplo: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] → true. Com [[0,1],[1,2],[2,3],[1,3],[1,4]] → false (tem ciclo).

Carregando editor…

Tentou? Para checar se é uma árvore, você precisa de duas coisas: conexo e sem ciclo. O Union-Find detecta o ciclo elegantemente — quando uma aresta liga dois nós que já estavam no mesmo grupo.

A teoria: cada grupo tem um "representante"

A ideia do Union-Find: cada nó aponta para um "pai", e seguindo os pais você chega ao representante (raiz) do grupo. Dois nós estão no mesmo grupo se têm o mesmo representante. Duas operações:

find(x): sobe pelos pais até a raiz — o representante do grupo de x.
union(a, b): liga a raiz de um grupo à raiz do outro, fundindo-os.

parent = [0, 1, 2, 3, 4]   # no início, cada nó é seu próprio grupo

union(0,1): parent[0] = 1      grupos: {0,1} {2} {3} {4}
union(2,3): parent[2] = 3      grupos: {0,1} {2,3} {4}
find(0) == find(1)? sim → conectados
find(0) == find(2)? não → grupos diferentes

Duas otimizações deixam cada operação quase O(1) (amortizado, O(α(n)) — praticamente constante):

Compressão de caminho: no find, aponte os nós direto para a raiz.
União por tamanho/altura: ligue sempre a árvore menor sob a maior.

Detectar ciclo com Union-Find

Eis a sacada para grafos não-dirigidos: ao processar uma aresta (a, b), se a e b já têm o mesmo representante, então já havia um caminho entre eles — esta aresta fecha um ciclo. Se têm representantes diferentes, una-os.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # compressão
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False        # já conectados ⇒ ciclo!
        self.parent[ra] = rb
        return True             # fundiu dois grupos

Carregando editor…

Graph Valid Tree, em uma frase

Uma árvore com n nós tem exatamente n-1 arestas e é conexa. Com Union-Find: se não houver n-1 arestas, já não é árvore; senão, una cada aresta — se alguma fechar um ciclo (union retorna False), não é árvore. Com n-1 arestas e nenhum ciclo, o grafo é forçosamente conexo. Quase O(n + e).

Union-Find ou DFS/BFS?

Os dois acham componentes conexos. Quando preferir Union-Find?

Situação	Melhor
Componentes de um grafo estático	DFS/BFS ou Union-Find (tanto faz)
Arestas chegando aos poucos ("conectou agora?")	Union-Find (atualiza em ~O(1))
Detectar ciclo em grafo não-dirigido	Union-Find (aresta dentro do mesmo grupo)
Precisa do caminho ou da ordem de visita	DFS/BFS

🧠 Quiz de fixação

0/4

1. Como o Union-Find decide se dois nós estão no mesmo grupo?

2. Como o Union-Find detecta um ciclo num grafo não-dirigido?

3. Por que uma árvore válida com n nós precisa de exatamente n-1 arestas?

4. Quando o Union-Find é claramente preferível a DFS/BFS?

Resumo

Union-Find: cada grupo tem um representante; find acha a raiz, union funde grupos. Quase O(1) por operação (com compressão de caminho).
Detecta ciclo (não-dirigido): aresta entre nós já do mesmo grupo.
Graph Valid Tree: n-1 arestas + sem ciclo ⇒ árvore.
Prefira Union-Find para conexões dinâmicas e detecção de ciclo não-dirigido.

Próxima aula: lembrar que grid é grafo — e propagar de várias fontes ao mesmo tempo.

Todas as aulas da seção