백준 11400번 단절선

< 백준 11400번 단절선 - 마포 코딩박 >

사용한 알고리즘: DFS


 단절선을 구하는 문제입니다. DFS 한번 도는거 만으로 풀 수 있습니다.

문제풀이는 다음과 같습니다.

(1) (코드 47~52)
 양방향 간선이므로 정점 a, b가 연결되어 있으면, 각 정점의 자식노드로 다른 정점을 저장합니다.

(2) (코드 15~39, 53~55)
 아직 방문하지 않은 정점을 DFS 로 돌릴 것입니다.
 Root 노드에서 자식노드를 다시 DFS로 돌려가면서 노드별로 번호(dfsn)를 매겨줍니다.
 DFS를 재귀적으로 돌릴 때 바로 직전에서 온 노드로는 돌아보지 않습니다.
 자식 노드가 자신의 번호(dfsn) 이상을 갈 수 없는 경우 해당 자식과의 간선이 단절선입니다.