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 再帰呼び出しをほどきながら) エッジが not のブリッジであるかどうかを確認できます。

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