在无向图中寻找桥梁？

Question

图中的桥意味着如果我们删除它，图将断开连接！ ，所以我想知道是否有办法找到一个图所有桥梁： 这里有一个例子：

input 
    12 15 
    1 2 
    1 3 
    2 4 
    2 5 
    3 5 
    4 6 
    6 7 
    6 10 
    6 11 
    7 8 
    8 9 
    8 10 
    9 10 
    10 11 
    11 12 

Output : 

    2 4 
    4 6 
    11 12 

请不要给我一个方案只是一个提示！ 谢谢

Answer 1

如果你有图G中每个顶点v的访问号vn [v]和low number low [v]，那么你可以找到一个边是否是桥（当展开dfs递归调用时）使用以下条件

if (low[w] > vn[v]) then (v,w) is a bridge