graph - 在无向图中寻找桥梁？

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[v]，那么您可以使用以下条件找到一条边是否是非桥（在展开 dfs 递归调用时）

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