DSU com Compressão de Caminhos
Encontre e una em tempo quase constante.
DSU com Compressão de Caminhos é uma aula grátis de Competitive Programming Academy 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 Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que um DSU acompanha
Uma união de conjuntos disjuntos mantém os itens agrupados em conjuntos que não se sobrepõem, permitindo verificar se dois elementos já pertencem ao mesmo grupo. 🤝
Conjuntos como árvores
O DSU armazena cada conjunto como uma árvore. Cada elemento aponta para um pai, e o nó mais alto, a raiz, é o nome único de todo o grupo.
O vetor de pais
Você mantém todas essas ligações em um único vetor. Comece com cada elemento como seu próprio pai, indicando que cada item começa em um conjunto separado.
parent = list(range(n))Encontre a raiz
A operação find percorre as ligações de pais até que um elemento aponte para si mesmo. Esse nó que aponta para si próprio é a raiz que identifica o conjunto.
while parent[x] != x:
x = parent[x]Cadeias longas prejudicam
Sem cuidado, os conjuntos podem formar cadeias longas e estreitas. Nesse caso, find percorre os nós um a um, e uma única consulta pode custar O(n), o que é lento demais.
Entra a compressão de caminhos
A compressão de caminhos resolve isso: enquanto encontra a raiz, você faz cada nó visitado apontar diretamente para ela, achatando a árvore para a próxima vez. ⚡
Compressão recursiva
A maneira mais simples é usar recursão. Encontre a raiz e depois armazene-a novamente em parent[x] antes de retornar, encurtando permanentemente a ligação.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Dois itens pertencem ao mesmo conjunto?
Para testar se dois elementos estão conectados, compare suas raízes. Se find(a) for igual a find(b), eles pertencem ao mesmo grupo; caso contrário, continuam separados.
if find(a) == find(b):
print("connected")Una dois conjuntos
A operação union une grupos fazendo uma raiz apontar para a outra. Uma linha conecta duas árvores inteiras em um único conjunto.
def union(a, b):
parent[find(a)] = find(b)Por que é tão rápido
Somente com a compressão, as operações são executadas em aproximadamente O(log n) de tempo amortizado; combinadas com a classificação, chegam a um tempo quase constante por consulta.
Onde o DSU se destaca
O DSU é essencial para questões de conectividade: círculos de amizade, componentes de redes e a árvore geradora de Kruskal dependem de find e union rápidos. 🌐
Verificação rápida
Pense no que a compressão de caminhos realmente altera.
Recapitulação
Você construiu um DSU: um vetor de pais, find para obter a raiz e union para unir conjuntos. A compressão de caminhos o mantém extremamente rápido. Muito bem! 🎉
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 Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “DSU com Compressão de Caminhos”?
Encontre e una em tempo quase constante. Você pratica Competitive Programming Academy 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 Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy 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 Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy 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 Componentes
- Árvore Geradora Mínima de Kruskal
- MST de Prim com uma Heap