[20040] Union-find로 그래프 상의 사이클 검출

20040번: 사이클 게임

아이디어: 매번 DFS돌리며 사이클을 검출하려면 TLE가 발생하니 각 노드를 하나의 집합으로 두고 같은 집합끼리 묶으려 하면 사이클임을 알 수 있다.

결국 DFS가 아닌 Union-find를 쓰는 문제이나,

노드의 숫자인 N= 500,000이며 merge시행 횟수인 M= 1,000,000 이므로 O(N)으로 Union-find를 하면 TLE

따라서 find과정에서 만나는 과정마다 부모를 최상위 노드로 설정해가며 O(logN)으로 만들 필요가 있었다.

int find(int cur){
  if(uni[cur]==cur)return cur;
  // 경로압축을 위해 만나는 노드마다 부모를 자신의 최상위 노드로 설정
  else return uni[cur]=find(uni[cur]);
}

find를 통하여 최상위 노드를 알아낸 뒤, 크기를 비교하여 작은 쪽을 큰 쪽으로 붙여주면 끝.

이를 모든 경로상에 대하여 진행하여주고 find(a) == find(b)라면 같은 유니언끼리 붙이려하는 상황이니 횟수 출력 후 종료를 하면된다.