무향 그래프에서 브릿지 찾기?

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]와 낮은 번호 [v]가있는 경우 가장자리가 브리지가 아닌지 (dfs 재귀 호출을 푸는 동안) 다음 조건을 사용하십시오.

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