离散数学:删除顶点后检查图形的连通性？有效的方式？

Question

第一:我承认它是编程竞赛的一部分(赢得胜利的东西或其他东西)

我在阅读了问题并尝试了以下算法后得出以下结论.

给定Undirected Connected Graph of nvertices,

count = 0
For i=1 to n:
  remove(ith vertex)
  check for connectivity of graph with remaining vertices
  if connected 
    then increment count
  attach the removed vertex back
print count

我已经通过两种方式实现了这个:(1)DFS(2)Disjoint-Set Union,但没有一种算法足以获得AC.是否有更好的方法可以做到这一点？我不需要详细的解释,几句话就会做,休息我会弄清楚或者死的尝试:p.谢谢!

Answer 1

移除图形断开的顶点称为铰接点.所有在图铰接点可以在线性时间内找到.