Estrutura de dados para rastrear elementos particionados em conjuntos disjuntos, com operações quase O(1) para unir conjuntos e verificar conectividade.
Union-Find (ou Disjoint Set Union - DSU) é uma estrutura de dados que mantém uma coleção de conjuntos disjuntos. Ela suporta duas operações principais: Find: descobre a qual conjunto um elemento pertence, retornando o "representante" (raiz) do conjunto. Union: une dois conjuntos em um só. A mágica está em duas otimizações que tornam as operações quase O(1): Path Compression: quando fazemos Find, fazemos todos os elementos no caminho apontarem diretamente para a raiz, achatando a árvore para buscas futuras. Union by Rank: sempre anexamos a árvore menor na maior, mantendo a altura logarítmica. Com ambas otimizações, a complexidade amortizada é O(α(n)), onde α é a função inversa de Ackermann - cresce tão devagar que para todos os fins práticos é constante (α(n) <= 4 para n até 10^80).
“Path compression achata a árvore durante Find, e union by rank mantém árvores balanceadas. Juntos, tornam operações praticamente O(1).”
alpha(n) é a função inversa de Ackermann, praticamente constante.
Com path compression e union by rank, qualquer sequência de m operações em n elementos leva O(m * alpha(n)) tempo.
Arrays parent e rank com n elementos.
Se o elemento já aponta para a raiz.
Mesmo no pior caso, alpha(n) <= 4 para valores práticos.
| Algoritmo | Tempo | Espaco | Melhor Para |
|---|---|---|---|
| Union-Find(atual) | O(alpha(n)) amortizado | O(n) | Conectividade dinâmica, Kruskal MST |
| DFS/BFS | O(V + E) | O(V) | Travessia única, caminho mais curto |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1class UnionFind:Definição da Classe2 def __init__(self, n):Definição da Classe3 self.parent = list(range(n))Inicializar Parent4 self.rank = [0] * nInicializar Rank5 6 def find(self, x):Operação Find7 if self.parent[x] != x:Operação Find8 self.parent[x] = self.find(self.parent[x])Path Compression9 return self.parent[x]Operação Find10 11 def union(self, x, y):Operação Union12 px, py = self.find(x), self.find(y)Operação Union13 if px == py:Verificar Conexão14 return False # Ja conectadosVerificar Conexão15 16 # Union by rankUnion by Rank17 if self.rank[px] < self.rank[py]:Union by Rank18 px, py = py, pxUnion by Rank19 self.parent[py] = pxUnion by Rank20 if self.rank[px] == self.rank[py]:Union by Rank21 self.rank[px] += 1Union by Rank22 return True23 24 def connected(self, x, y):Verificar Conexão25 return self.find(x) == self.find(y)Verificar Conexão26 27 28# Exemplo: detectar ciclo29def has_cycle(n, edges):30 uf = UnionFind(n)31 for u, v in edges:32 if not uf.union(u, v):33 return True # Ciclo encontrado34 return False35