Tive uma idéia pra resolver o problema da manutenção, mas não sei se ela é válida: eu modifiquei o all_bridges() para devolver, em ordem crescente, todos os vértices que fazem parte de uma ponte e tem ao menos um vizinho além do vértice da outra ponta. Implementei isso mas dá wrong answer. Alguém sabe me dizer se a minha idéia está errada?
Tive uma idéia pra resolver o problema da manutenção, mas não sei se ela é válida: eu modifiquei o all_bridges() para devolver, em ordem crescente, todos os vértices que fazem parte de uma ponte e tem ao menos um vizinho além do vértice da outra ponta. Implementei isso mas dá wrong answer. Alguém sabe me dizer se a minha idéia está errada?Sim, você deve adaptar o all_briges(), mas a sua função deve encontar vértices de articução.
Um vértice de articulação pode não pertencer a ponte alguma.
Existe um slide de Portugal que me ajudou a resolver o problema: http://paginas.fe.up.pt/~jpf/teach/AEDII/grafos3.pdf . Lá tem um algoritmo que fala sobre articulações. Não é exatamente a solução do problema (você precisará modificá-lo um pouco), mas ajuda bastante.