União por classificação e limite do inverso de Ackermann
Adicione união baseada em classificação para manter as árvores baixas e entenda por que as otimizações combinadas produzem O(alpha(n)) amortizado — efetivamente constante.
União por classificação e limite do inverso de Ackermann é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 2 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.
Por que as árvores ficam altas sem classificação
A compressão de caminho simples impede árvores altas depois das travessias, mas, durante as operações de união iniciais, ainda podemos construir uma árvore alta se sempre anexarmos a raiz da árvore maior à árvore menor. A união por classificação resolve isso acompanhando o limite superior da altura da árvore (a classificação) e sempre anexando a árvore mais baixa à mais alta.
A classificação não é exatamente a altura — a compressão de caminho pode reduzir a altura para abaixo da classificação —, mas é um limite superior. Mantendo a árvore mais alta como a nova raiz, garantimos que a classificação só aumente quando duas árvores com a mesma classificação forem mescladas, limitando a classificação máxima a O(log n).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n # initially all trees have rank 0
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:
return False
# Attach lower-rank tree under higher-rank tree
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 # only increases when ranks are equal
return TrueOs três casos da união por classificação
Ao mesclar dois componentes com raízes px e py, surgem três casos com base em suas classificações:
- classificação[px] > classificação[py]: anexe py sob px — a classificação de px não muda
- classificação[px] < classificação[py]: anexe px sob py — a classificação de py não muda
- classificação[px] == classificação[py]: anexe py sob px (ou vice-versa) — a classificação da nova raiz aumenta em 1
A classificação só é incrementada no caso de classificações iguais. Isso significa que a classificação n exige pelo menos 2^n nós, portanto a classificação máxima é O(log n). Isso mantém os caminhos de find curtos mesmo sem compressão de caminho.
# Illustrating rank behaviour with 8 nodes
dsu_parent = list(range(8))
dsu_rank = [0] * 8
def find(x):
while dsu_parent[x] != x:
x = dsu_parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return
if dsu_rank[px] < dsu_rank[py]:
px, py = py, px
dsu_parent[py] = px
if dsu_rank[px] == dsu_rank[py]:
dsu_rank[px] += 1
# Build balanced tree step by step
union(0,1); union(2,3); union(4,5); union(6,7)
union(0,2); union(4,6)
union(0,4)
print('Ranks:', dsu_rank) # max rank <= log2(8) = 3
print('Root of all:', find(0))Combinação de compressão de caminho + união por classificação
Quando a compressão de caminho e a união por classificação são usadas em conjunto, o tempo amortizado por operação cai para O(alpha(n)) — a função inversa de Ackermann. Para qualquer tamanho de entrada prático (até 2^65536), alpha(n) é no máximo 4. Isso equivale, na prática, a tempo constante.
A compressão de caminho achata as árvores de baixo para cima após as travessias, enquanto a união por classificação impede que as árvores cresçam muito durante as mesclagens, de cima para baixo. Juntas, elas são complementares: a classificação limita a profundidade inicial, e a compressão elimina essa profundidade após a primeira travessia.
class OptimalDSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x): # path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y): # union by rank
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 = OptimalDSU(1000)
import random; random.seed(42)
for _ in range(5000):
dsu.union(random.randint(0,999), random.randint(0,999))
print('Max rank reached:', max(dsu.rank)) # stays very smallCompreendendo a função inversa de Ackermann
A função de Ackermann A(m, n) cresce extraordinariamente rápido — mais rápido do que qualquer função recursiva primitiva. Sua inversa, alpha(n), é definida como o menor m tal que A(m, m) >= n. Como a função de Ackermann cresce tão rapidamente, alpha(n) cresce de forma inimaginavelmente lenta.
Para n = 10^80 (o número de átomos no universo observável), alpha(n) ainda é apenas 4. É por isso que a DSU com as duas otimizações é tratada como tendo tempo efetivamente constante em qualquer situação prática. Você nunca encontrará um problema real grande o suficiente para que alpha(n) ultrapasse 5.
# Showing how slowly alpha(n) grows
# alpha(n) = smallest m such that A(m,m) >= n
# A(0,n) = n+1
# A(1,n) = n+2
# A(2,n) = 2n+3
# A(3,n) = 2^(n+3) - 3
# A(4,4) = 2^(2^(2^(2^2))) - 3 which is astronomically large
alpha_thresholds = {
1: 'n=1',
2: 'n up to 3',
3: 'n up to about 2048',
4: 'n up to 10^19728 (far beyond atoms in universe)',
5: 'essentially unreachable in practice',
}
for k, v in alpha_thresholds.items():
print(f'alpha(n)={k}: {v}')
print('\nConclusion: DSU operations are effectively O(1) for all real inputs.')Classificação versus tamanho: qual usar?
Uma alternativa à união por classificação é a união por tamanho: sempre anexe a árvore de menor tamanho à árvore de maior tamanho. As duas abordagens oferecem a mesma garantia de altura O(log n). A união por tamanho costuma ser mais fácil de compreender porque os tamanhos são contagens exatas, enquanto as classificações são limites superiores que podem não refletir a altura verdadeira após a compressão.
Em entrevistas, qualquer uma das abordagens é aceitável. A união por tamanho ainda oferece a vantagem de fornecer gratuitamente os tamanhos dos componentes, algo exigido por muitos problemas. A união por classificação é um pouco mais elegante do ponto de vista teórico e corresponde à demonstração original de Tarjan do limite da função inversa de Ackermann.
class DSUBySize:
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 False
if self.size[px] < self.size[py]:
px, py = py, px # always attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
return True
dsu = DSUBySize(8)
for u, v in [(0,1),(2,3),(0,2),(4,5),(6,7),(4,6),(0,4)]:
dsu.union(u, v)
print('Size of giant component:', dsu.size[dsu.find(0)])Esboço da demonstração: por que a classificação permanece em O(log n)
Podemos provar por indução que uma árvore DSU com classificação r contém pelo menos 2^r nós. Caso base: a classificação 0 significa um único nó (2^0 = 1). Passo indutivo: a classificação r só aumenta quando duas árvores de classificação r-1 iguais são mescladas. Pela hipótese de indução, cada subárvore tem pelo menos 2^(r-1) nós, portanto a árvore mesclada tem pelo menos 2 × 2^(r-1) = 2^r nós.
Como uma árvore de classificação r tem pelo menos 2^r nós e temos n nós no total, a classificação máxima é no máximo log₂(n). Isso significa que find sem compressão de caminho leva O(log n) tempo e, com compressão de caminho, o custo amortizado cai muito mais.
# Verify the 2^rank lower bound empirically
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * 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.rank[px] < self.rank[py]: px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
if self.rank[px] == self.rank[py]: self.rank[px] += 1
n = 32
dsu = DSU(n)
for i in range(n - 1): dsu.union(i, i + 1)
for root in range(n):
if dsu.find(root) == root:
r = dsu.rank[root]
print(f'Root {root}: rank={r}, size={dsu.size[root]}, 2^rank={2**r}')Modelo de DSU para programação competitiva
Em programação competitiva e entrevistas, você quer um modelo de DSU curto, correto, testado na prática e capaz de lidar com todos os casos-limite. O modelo abaixo usa a redução do caminho pela metade (compressão em uma passagem) combinada com a união por tamanho — uma combinação fácil de digitar rapidamente e que evita completamente a recursão.
Sempre inicialize parent[i] = i e size[i] = 1. Lembre-se de que, depois de find, o size da raiz representa o componente inteiro. Nunca use size[x] diretamente — sempre chame size[find(x)].
class DSU:
def __init__(self, n):
self.p = list(range(n))
self.sz = [1] * n
def find(self, x):
while self.p[x] != x:
self.p[x] = self.p[self.p[x]] # path halving
x = self.p[x]
return x
def union(self, x, y):
x, y = self.find(x), self.find(y)
if x == y: return False
if self.sz[x] < self.sz[y]: x, y = y, x
self.p[y] = x
self.sz[x] += self.sz[y]
return True
def same(self, x, y): return self.find(x) == self.find(y)
def size(self, x): return self.sz[self.find(x)]
# Usage
dsu = DSU(10)
dsu.union(0, 5)
dsu.union(5, 9)
print(dsu.same(0, 9)) # True
print(dsu.size(0)) # 3Quando a DSU não é suficiente
A DSU permite mesclar conjuntos, mas não permite dividir um conjunto novamente em dois. Se um problema exigir tanto unir quanto separar grupos, você precisará de uma estrutura diferente (como uma árvore de corte e ligação). A DSU também não armazena nativamente os elementos de cada grupo — você precisará de uma lista de adjacência ou de um dicionário adicional para isso.
Além disso, a DSU padrão não oferece suporte a arestas ponderadas sem modificações (a DSU ponderada é uma variante mais avançada). Para problemas como encontrar o caminho de menor custo entre nós conectados, Dijkstra ou BFS é mais apropriado. Reconhecer o escopo da DSU evita aplicá-la incorretamente.
# DSU is perfect for: connected-components, cycle detection,
# Kruskal's MST, accounts-merge, number-of-provinces
# DSU is NOT suitable for:
# - Splitting/removing edges from a group
# - Finding the actual path between two nodes
# - Storing all members of a group efficiently
# - Directed graphs (without modification)
# Example of storing group members alongside DSU
from collections import defaultdict
class DSUWithMembers:
def __init__(self, n):
self.p = list(range(n))
self.members = defaultdict(set)
for i in range(n): self.members[i].add(i)
def find(self, x):
while self.p[x] != x: self.p[x] = self.p[self.p[x]]; x = self.p[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
self.members[px] |= self.members[py]
del self.members[py]
self.p[py] = pxComparando DSU com BFS/DFS para conectividade
Tanto BFS/DFS quanto DSU resolvem consultas estáticas de conectividade, mas têm vantagens diferentes. BFS/DFS é executado em O(V + E) e pode encontrar o caminho real entre os nós. DSU responde a muitas consultas de conectividade sobre conjuntos de arestas que crescem incrementalmente, com custo próximo de O(1) por consulta — ideal para algoritmos on-line, nos quais as arestas chegam uma por vez.
Se você receber todas as arestas de antemão e precisar apenas da conectividade, qualquer uma das abordagens funcionará. Se as arestas chegarem dinamicamente e você precisar responder a consultas de conectividade entre cada nova aresta, DSU será claramente a melhor opção. Para problemas que também exigem o caminho mais curto, use BFS.
# Comparing DSU vs BFS for 1000 nodes, 2000 edges
# After all edges given => BFS works fine
# But with online edge arrival + interleaved queries => DSU shines
from collections import deque
def bfs_connected(graph, src, dst, n):
visited = set([src])
q = deque([src])
while q:
node = q.popleft()
if node == dst: return True
for nb in graph.get(node, []):
if nb not in visited:
visited.add(nb); q.append(nb)
return False
# DSU for same query:
# dsu.same(src, dst) -- O(alpha(n)) amortised
# BFS for same query:
# O(V + E) every time -- not suitable for repeated queries
print('DSU is preferred for repeated connectivity queries.')
print('BFS/DFS is preferred when you also need the actual path.')Prática: árvore geradora mínima com DSU
O algoritmo de Kruskal para árvore geradora mínima usa DSU diretamente. Ordene todas as arestas por peso e, em seguida, adicione cada aresta de forma gulosa se suas extremidades estiverem em componentes diferentes (sem formar um ciclo). DSU fornece a verificação de ciclos com custo próximo de O(1). O resultado é uma MST com n-1 arestas.
Esta é uma demonstração clássica do poder de DSU: ele transforma uma verificação ingênua de ciclos de O(E × V) em um processo O(E × alpha(n)). Com a ordenação em E log E, o tempo total de Kruskal é O(E log E), e as operações de DSU são tão rápidas que se tornam insignificantes em comparação com a ordenação.
def kruskal(n, edges):
edges.sort(key=lambda e: e[2]) # sort by weight
parent = list(range(n))
rank = [0] * 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: return False
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
mst_weight = 0
mst_edges = []
for u, v, w in edges:
if union(u, v):
mst_weight += w
mst_edges.append((u, v, w))
return mst_weight, mst_edges
edges = [(0,1,4),(0,2,3),(1,2,1),(1,3,2),(2,3,5)]
w, e = kruskal(4, edges)
print('MST weight:', w) # 6: edges (1,2,1)+(1,3,2)+(0,2,3)
print('MST edges:', e)DSU com Rollback: conectividade off-line
O DSU padrão não oferece suporte a operações de desfazer. No entanto, o DSU com rollback (também chamado de DSU com histórico) oferece: em vez de usar compressão de caminhos (que é difícil de desfazer), use apenas union por classificação e registre cada operação union em uma pilha. Para fazer rollback, retire um item da pilha com pop e restaure o pai e a classificação. Isso permite resolver problemas de conectividade dinâmica off-line, nos quais as arestas podem ser adicionadas e removidas.
Embora esta seja uma variante avançada, raramente vista em entrevistas padrão, ela demonstra que union por classificação é o invariante crucial — não a compressão de caminhos. Sem compressão de caminhos, cada operação find custa O(log n) e, com rollback, as operações da pilha custam O(1), resultando em O(log n) por operação no total, em vez de O(alpha(n)).
class DSUWithRollback:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.history = [] # stack of (node, old_parent, node2, old_rank)
def find(self, x): # NO path compression (cannot undo)
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: return False
if self.rank[px] < self.rank[py]: px, py = py, px
# Record state before modifying
self.history.append((py, self.parent[py], px, self.rank[px]))
self.parent[py] = px
if self.rank[px] == self.rank[py]: self.rank[px] += 1
return True
def rollback(self):
py, old_par_py, px, old_rank_px = self.history.pop()
self.parent[py] = old_par_py
self.rank[px] = old_rank_px
dsu = DSUWithRollback(5)
dsu.union(0, 1); dsu.union(1, 2)
print('0 and 2 connected:', dsu.find(0) == dsu.find(2)) # True
dsu.rollback()
print('After rollback:', dsu.find(0) == dsu.find(2)) # FalseVerificaçã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: union por classificação sempre anexa a árvore mais rasa à árvore mais profunda, a classificação aumenta apenas quando duas árvores com a mesma classificação são mescladas, mantendo a altura da árvore em O(log n) e combinar a compressão de caminhos com union por classificação alcança O(alpha(n)) amortizado — efetivamente tempo constante. A seguir, aplicaremos o DSU completo e otimizado à conexão redundante e à detecção de ciclos em grafos.
Perguntas Frequentes
A aula “União por classificação e limite do inverso de Ackermann” é grátis?
Sim — o texto completo de “União por classificação e limite do inverso de Ackermann” é 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 “União por classificação e limite do inverso de Ackermann”?
Adicione união baseada em classificação para manter as árvores baixas e entenda por que as otimizações combinadas produzem O(alpha(n)) amortizado — efetivamente constante. 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 2 de 4.
Quanto tempo leva a aula “União por classificação e limite do inverso de Ackermann”?
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