DSU com compressão de caminhos
Implemente find com compressão de caminhos para que todos os nós do caminho apontem diretamente para a raiz, alcançando um custo amortizado próximo de O(1) para find.
DSU com compressão de caminhos é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
O que é a União-Busca?
Disjoint Set Union (DSU), também chamada de União-Busca, é uma estrutura de dados que mantém uma coleção de conjuntos disjuntos (sem sobreposição). Ela oferece duas operações essenciais: find (a qual conjunto pertence o elemento x?) e union (mesclar os conjuntos que contêm x e y). A DSU é ideal para problemas de conectividade dinâmica, nos quais os grupos se unem ao longo do tempo, mas nunca se dividem.
Cada elemento começa em seu próprio conjunto. À medida que processamos arestas ou relações, mesclamos os conjuntos. O desafio é fazer isso com eficiência — implementações ingênuas custam O(n) por operação, mas, com otimizações, aproximamo-nos de O(1) amortizado.
# Naive DSU without optimisations
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # each node is its own parent
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = pyO problema do find ingênuo
Na DSU ingênua, find(x) percorre a cadeia de pais até chegar a um nó que aponta para si mesmo (a raiz). Se a árvore estiver balanceada, isso é O(log n). Porém, se sempre fizermos a união colocando a segunda raiz sob a primeira, podemos criar uma cadeia (árvore degenerada) de comprimento n, fazendo com que cada find seja O(n).
Considere unir 0→1→2→3→4 em sequência. A chamada de find do nó 0 precisa percorrer toda a cadeia. Com a compressão de caminho, eliminamos esse problema fazendo cada nó visitado apontar diretamente para a raiz durante a própria operação de find.
# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4] => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4] => find(0) takes 1 step
parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
x = parent[x]
steps += 1
print('Root:', x, 'Steps taken:', steps)Compressão de caminho: recursiva em uma passagem
A compressão de caminho modifica a operação de find para que, depois de encontrar a raiz, cada nó ao longo do caminho seja atualizado para apontar diretamente para ela. As chamadas futuras de find nesses nós tornam-se O(1). A versão recursiva consegue isso de forma elegante em uma única passagem.
A ideia principal é: depois que a chamada recursiva retorna a raiz, definimos self.parent[x] = root antes de retornar. Isso achata a árvore — todos os nós no caminho da busca passam a apontar diretamente para a raiz. Isso não altera a qual conjunto um nó pertence; apenas encurta os caminhos de busca futuros.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)Compressão de caminho: iterativa em duas passagens
A versão iterativa da compressão de caminho usa duas passagens: a primeira percorre os pais até encontrar a raiz; a segunda revisita cada nó do caminho e atualiza seu pai para apontar diretamente para a raiz. Isso evita a sobrecarga da pilha de recursão e é seguro para árvores muito profundas, próximas do limite de recursão do Python.
Nas abordagens recursiva e iterativa, a correção não muda — find ainda retorna a mesma raiz. A única diferença é que os ponteiros para os pais são atualizados como efeito colateral, fazendo com que todos os finds futuros nesses nós sejam O(1).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root] # first pass: find root
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root # second pass: compress
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
return True
return False # already connected
dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after find(0):', dsu.parent[:])Complexidade amortizada da compressão de caminho
A compressão de caminho sozinha alcança um tempo amortizado de O(log n) por operação em uma sequência de m operações. Cada operação de find pode ser dispendiosa na primeira vez que uma cadeia é percorrida, mas ela achata essa cadeia, fazendo com que cada find posterior nesses nós seja O(1). O trabalho total é distribuído entre muitas operações.
A análise formal usa o método da função potencial: o potencial da DSU diminui sempre que o caminho até o pai de um nó encurta, e essa diminuição paga o custo da travessia. Sem a união por classificação, a compressão de caminho sozinha fornece O(log n) amortizado — uma melhoria enorme em relação ao O(n) ingênuo.
# Demonstrating amortised benefit
import time
def build_chain(n):
parent = list(range(n))
for i in range(n - 1):
parent[i] = i + 1 # chain: 0->1->2->...->n-1
return parent
n = 1000
parent = build_chain(n)
# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
root = parent[root]
# Compress
while parent[x] != root:
nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0]) # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')Contagem de componentes conectados
Uma aplicação comum da DSU é contar componentes conectados em um grafo. Inicializamos um contador components igual a n (um para cada nó). Cada união bem-sucedida (mesclando dois conjuntos diferentes) decrementa o contador em 1. No final, o contador contém o número de componentes distintos.
Isso é mais eficiente do que executar BFS ou DFS para consultas de conectividade, especialmente quando as arestas chegam incrementalmente, à medida que são recebidas. A DSU processa cada aresta em tempo amortizado quase O(1), independentemente de quando ela chega.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
self.parent[px] = py
self.components -= 1
return True
dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
dsu.union(u, v)
print('Components:', dsu.components) # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')DSU para problemas de grafos: número de províncias
O problema Número de províncias fornece uma matriz de adjacência n×n e pergunta quantos grupos de cidades conectadas direta ou indiretamente existem. Esse é exatamente um problema de componentes conectados que a DSU resolve com clareza. Percorremos todos os pares (i, j) em que isConnected[i][j] == 1 e chamamos union(i, j).
Depois de processar todas as conexões, dsu.components é a resposta. Isso é mais simples e rápido do que executar BFS a partir de cada nó ainda não visitado, além de lidar diretamente com a representação em matriz, sem precisar criar primeiro uma lista de adjacência.
def find_provinces(isConnected):
n = len(isConnected)
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px != py:
parent[px] = py
return True
return False
count = n
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
if union(i, j):
count -= 1
return count
matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix)) # 2: cities {0,1} and {2}Variantes da compressão de caminho: redução pela metade
Além da compressão em duas passagens, existe uma variante mais simples de uma passagem chamada redução do caminho pela metade: enquanto percorremos a cadeia, fazemos cada nó apontar para seu avô em vez de seu pai. Isso reduz pela metade o comprimento do caminho a cada travessia, sem uma segunda passagem, e alcança a mesma complexidade amortizada O(alpha(n)) quando combinada com a união por classificação.
A redução do caminho pela metade costuma ser preferida na programação competitiva porque consiste em um único laço simples, sem recursão nem uma segunda travessia. Cada passo executa self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x].
class DSUHalving:
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]] # point to grandparent
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))Verificando a conectividade após as uniões
Para verificar se dois nós estão connected (no mesmo componente), chame find(x) == find(y). Se ambos retornarem a mesma raiz, eles estarão no mesmo componente. Essa é a consulta de connected e, com a compressão de caminho, é executada em tempo amortizado próximo de O(1).
Em problemas de entrevistas, as consultas de conectividade geralmente aparecem intercaladas com operações de união. A DSU lida com ambas on-line — você pode alternar entre uniões e consultas em qualquer ordem. Isso diferencia a DSU de algoritmos para grafos estáticos, como BFS/DFS, que precisam ser executados novamente após cada mudança estrutural.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
def connected(self, x, y):
return self.find(x) == self.find(y)
dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7)) # True: 0-3-7
print(dsu.connected(0, 5)) # False: different components
print(dsu.connected(1, 5)) # True: 1-5Erros comuns na implementação da DSU
Um erro frequente é chamar find e depois modificar parent incorretamente. Sempre chame find nos dois elementos antes de verificar a igualdade — caso contrário, você pode comparar incorretamente um nó com sua própria raiz. Outro erro comum é esquecer que union deve não fazer nada quando os dois elementos já compartilham a mesma raiz.
Em Python, o limite de profundidade da recursão (1000 por padrão) pode causar RecursionError para cadeias grandes com find recursivo. Use a versão iterativa em duas passagens, aumente o limite com sys.setrecursionlimit ou use a redução iterativa do caminho pela metade para evitar completamente a recursão profunda.
import sys
sys.setrecursionlimit(10000) # needed for large recursive DSU
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
# Safe iterative path compression
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root:
nxt = self.parent[x]
self.parent[x] = root
x = nxt
return root
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # already same component — do nothing
self.parent[px] = py
return True
dsu = DSU(5)
print(dsu.union(0, 1)) # True: merged
print(dsu.union(0, 1)) # False: already merged — no double-countingAcompanhamento do tamanho na DSU
Em alguns problemas, você precisa do tamanho de cada componente, não apenas de sua raiz. Adicione uma matriz size inicializada com 1 em todas as posições. Ao mesclar dois componentes, adicione o tamanho da raiz menor à raiz maior. Isso permite consultas do tamanho do componente em O(1) após qualquer união.
O acompanhamento do tamanho também é a base da união por tamanho (uma alternativa à união por classificação): sempre anexe a árvore menor à raiz da árvore maior. Isso garante que a altura da árvore permaneça O(log n), oferecendo a mesma garantia assintótica da união por classificação.
class DSUWithSize:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.size[px] < self.size[py]:
px, py = py, px # attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
def get_size(self, x):
return self.size[self.find(x)]
dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0)) # 3
print('Size of component containing 3:', dsu.get_size(3)) # 2
print('Size of component containing 5:', dsu.get_size(5)) # 1Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para entrevistas de programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: a DSU mantém conjuntos disjuntos com as operações find e union, a compressão de caminho achata a árvore fazendo todos os nós percorridos apontarem diretamente para a raiz e isso oferece um desempenho amortizado de find próximo de O(1). Em seguida, exploraremos a união por classificação, que mantém as árvores baixas de cima para baixo para alcançar o limite da função inversa de Ackermann.
Perguntas Frequentes
A aula “DSU com compressão de caminhos” é grátis?
Sim — o texto completo de “DSU com compressão de caminhos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “DSU com compressão de caminhos”?
Implemente find com compressão de caminhos para que todos os nós do caminho apontem diretamente para a raiz, alcançando um custo amortizado próximo de O(1) para find. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “DSU com compressão de caminhos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- DSU com compressão de caminhos
- União por classificação e limite do inverso de Ackermann
- Conexão redundante e detecção de ciclos
- Fusão de contas e componentes conexos