União por Classificação e Componentes
Mantenha as árvores baixas e conte os grupos.
União por Classificação e Componentes é uma aula grátis de Coding 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 Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
A união pode ser ingênua
A união simples apenas coloca uma raiz abaixo da outra. Se for feita sem cuidado, ela pode construir uma árvore alta e lenta; por isso, precisamos de uma maneira mais inteligente de unir as raízes.
A ideia principal
A união por classificação sempre anexa a árvore mais curta sob a mais alta. Manter as árvores baixas torna cada find posterior mais rápido. 📏
O que significa classificação
Classificação é uma estimativa da altura de uma árvore. Cada elemento começa com classificação 0, pois um único nó não tem profundidade abaixo dele.
rank = [0] * nAnexe a menor à maior
Compare as classificações das duas raízes. A raiz com a menor classificação torna-se filha, para que a árvore combinada permaneça o mais plana possível.
if rank[ra] < rank[rb]:
parent[ra] = rbEmpates aumentam a classificação
Quando as duas raízes têm a mesma classificação, escolha qualquer uma como nova raiz e aumente sua classificação em um, pois a árvore acabou de crescer um nível.
else:
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1Variação: união por tamanho
Uma alternativa popular é a união por tamanho: anexe o conjunto menor ao maior. Ela é igualmente eficaz e fornece os tamanhos dos grupos sem custo adicional.
Conte os componentes
Comece uma contagem em n, pois cada elemento é seu próprio grupo. Cada union bem-sucedido une dois grupos em um só, portanto diminua a contagem.
components = nIgnore uniões sem efeito
Se dois elementos já compartilharem uma raiz, o union não fará nada. Diminua a contagem somente quando as raízes forem realmente diferentes.
if find(a) != find(b):
union(a, b)
components -= 1Classificação mais compressão
Combine a união por classificação com a compressão de caminhos e o DSU será executado em tempo inverso de Ackermann, que é efetivamente constante para qualquer entrada real. ⚡
Tamanhos dos grupos sob demanda
Com a união por tamanho, você pode descobrir instantaneamente o tamanho de qualquer grupo: basta ler o tamanho armazenado na raiz do elemento.
group = size[find(x)]Onde isso é útil
A contagem de componentes responde a perguntas clássicas, como quantos círculos de amizade ou regiões conectadas existem após uma sequência de chamadas de união. 🌐
Verificação rápida
Analise como o contador de componentes muda.
Recapitulação
Você aprendeu a usar a união por nível para manter as árvores baixas e a acompanhar a quantidade de componentes e o tamanho dos grupos. DSU agora está extremamente rápido! 🎉
Perguntas Frequentes
A aula “União por Classificação e Componentes” é grátis?
Sim — o texto completo de “União por Classificação e Componentes” é 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 Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “União por Classificação e Componentes”?
Mantenha as árvores baixas e conte os grupos. Você pratica Coding 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 Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding 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 Componentes”?
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 Coding Interview Prep?
Sim. Cada aula de Coding 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 Componentes
- Árvore Geradora Mínima de Kruskal
- MST de Prim com uma Heap