Pontes e Pontos de Articulação
Encontre arestas e nós cuja remoção desconecta o grafo.
Pontes e Pontos de Articulação é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 4 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.
Pontos frágeis em um grafo
Algumas partes de um grafo não direcionado são críticas: remova-as e o grafo se dividirá. Encontrá-las revela as conexões frágeis.
O que é uma ponte
Uma ponte é uma aresta cuja remoção aumenta o número de componentes conexos. Ela é o único caminho entre duas regiões.
O que é um ponto de articulação
Um ponto de articulação é um nó cuja remoção desconecta o grafo. As redes são vulneráveis a esses pontos únicos de falha.
Árvores de DFS novamente
Ambos executam um único DFS, acompanhando o tempo de descoberta e um valor de low, de modo parecido com Tarjan, mas em um grafo não direcionado.
disc = [-1] * n
low = [-1] * nLow indica o alcance mais antigo
O low de um nó é o menor identificador de descoberta alcançável a partir de sua subárvore do DFS, possivelmente por meio de uma aresta de retorno para cima.
Inicialize ao entrar
Quando o DFS entra em um nó, atribua disc e low ao valor atual do temporizador e avance para os vizinhos.
disc[u] = low[u] = timer
timer += 1A condição de ponte
Depois de recursar no filho v, se low[v] > disc[u], nenhuma aresta de retorno passa por u, então a aresta u-v é uma ponte.
if low[v] > disc[u]:
bridges.append((u, v))A condição de articulação
Um u que não é raiz é um ponto de articulação quando um filho v satisfaz low[v] >= disc[u]: a subárvore de v não consegue contornar u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)O caso especial da raiz
A raiz do DFS é um ponto de articulação somente se tiver dois ou mais filhos na árvore do DFS, portanto conte-os.
if parent[u] == -1 and children > 1:
art.add(u)Ignore a aresta para o pai
Ao atualizar low a partir de uma aresta de retorno, não volte pela aresta até seu pai, ou você avaliará as pontes incorretamente.
if v != parent[u]:
low[u] = min(low[u], disc[v])Uma passagem, duas respostas
Um único DFS encontra todas as pontes e os pontos de articulação juntos em O(V + E). Nenhuma travessia adicional é necessária.
Verificação rápida
Depois de recursar no filho v a partir de u, você encontra low[v] > disc[u]. O que descobriu?
Recapitulação: arestas e nós críticos
Um único DFS com disc e low encontra tudo: low[v] > disc[u] indica uma ponte, e low[v] >= disc[u] indica um ponto de articulação. 🌉
Perguntas Frequentes
A aula “Pontes e Pontos de Articulação” é grátis?
Sim — o texto completo de “Pontes e Pontos de Articulação” é 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 “Pontes e Pontos de Articulação”?
Encontre arestas e nós cuja remoção desconecta o grafo. 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 4 de 4.
Quanto tempo leva a aula “Pontes e Pontos de Articulação”?
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