在無向圖中尋找橋樑？

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