Componentes Fortemente Conexos
Agrupe nós mutuamente alcançáveis com Tarjan.
Componentes Fortemente Conexos é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 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 SCC
Um componente fortemente conexo é um grupo máximo de nós em que cada nó pode alcançar todos os outros seguindo arestas direcionadas.
Por que isso importa
Colapsar cada SCC em um supernó transforma qualquer grafo direcionado em um DAG. Isso facilita o raciocínio sobre dependências mútuas.
Tarjan em uma passagem
O algoritmo de Tarjan encontra todos os SCCs em um único DFS. Ele executa em O(V + E), o mesmo custo de uma travessia simples.
Números de descoberta
Atribua a cada nó um tempo de descoberta na ordem em que o DFS o visita pela primeira vez. Esses identificadores permitem comparar qual nó foi visto antes.
disc = [-1] * n
timer = 0O valor de alcance mínimo
O valor de alcance mínimo de cada nó é o menor identificador de descoberta que pode ser alcançado a partir dele, inclusive por arestas de retorno. Ele ancora o componente.
low = [-1] * nColoque na pilha
Quando o DFS entra em um nó, defina seu disc e low e então empilhe o nó em uma pilha de nós que podem pertencer ao mesmo componente.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TrueAtualize low a partir dos filhos
Depois de recursar em um filho não visitado, propague seu valor de low para cima: low[u] torna-se o mínimo entre seu próprio valor e o low do filho.
dfs(v)
low[u] = min(low[u], low[v])Trate as arestas de retorno
Se um vizinho já estiver na pilha, ele é um ancestral deste SCC. Use seu disc para diminuir low[u].
elif on_stack[v]:
low[u] = min(low[u], disc[v])Identifique a raiz de um componente
Quando low[u] é igual a disc[u], o nó u é a raiz de um SCC. Tudo que estiver acima dele na pilha pertence ao mesmo componente.
Retire o componente da pilha
Em uma raiz, faça pop dos nós da pilha até remover u. O grupo retirado é exatamente um componente fortemente conexo.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju como alternativa
Prefere duas passagens? O algoritmo de Kosaraju executa o DFS, inverte todas as arestas e executa o DFS novamente na ordem de término para separar os SCCs.
Verificação rápida
Durante o DFS de Tarjan, o nó u satisfaz low[u] == disc[u]. O que isso indica?
Recapitulação: SCCs com Tarjan
Acompanhe disc e low em um único DFS, mantenha os nós ativos na pilha e retire um componente sempre que low for igual a disc. SCCs em O(V+E). 🧩
Perguntas Frequentes
A aula “Componentes Fortemente Conexos” é grátis?
Sim — o texto completo de “Componentes Fortemente Conexos” é 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 “Componentes Fortemente Conexos”?
Agrupe nós mutuamente alcançáveis com Tarjan. 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 3 de 4.
Quanto tempo leva a aula “Componentes Fortemente Conexos”?
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
- Ordenação Topológica com o Algoritmo de Kahn
- Detecte Ciclos em Grafos Direcionados
- Componentes Fortemente Conexos
- Pontes e Pontos de Articulação