Union-Find. [20040]

[1. 문제 설명]

Cycle 이 발생한 순서를 출력한다.

(없는 경우 0을 출력)

 

 

[2. 풀이 접근]

그래프에서 Cycle 을 감지하는 여러 방법이 있다.

 

A. dfs, bfs 중 한번 방문한 정점을 재 방문 하는 경우 (from->to->from 으로 가는 것은 제외)

B. union-find 를 이용하여 union 하지 않은 경우

 

union-find 자료구조는 최초 모든 집합은 자기 자신이 root 인 상태이며,

두 집합이 합쳐지면서, (두 정점이 서로 연결되면서)

그래프를 만들어 나가는데,

union 이 실패한다는 것은 두 노드가 이미 같은 집합(트리)에 있다는 것을 말하며,

이미 서로 연결되었다는 것을 의미하기도 한다.

(=> 직접 연결되었다는 것이 아니라, 다른 정점을 거쳐 연결된다.)

 

 

[3. 코드]