在无向图中寻找桥梁？

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