백준 20040 사이클 게임 - 파이썬

문제.

풀이.

유니온 파인드를 이용해서 풀면된다.

우선 생각해야 할게

유니온 연산을 하기전에 파인드 연산을 먼저해서 둘의 루트 노드가 같다면 사이클이 완성된것이다.

예를 들어

parent = [0, 1, 2, 3, 4, 5] 가 있고

이제부터 입력을 받는다고 한다면

0 1이 들어오면 둘의 파인드 연산을 했을때는 각각 루트 노드가 0 , 1이다

둘의 루트 노드가 다르니 유니온 연산을 시행한다

1, 2 입력이 들어오면 둘의 파인드 연산 결과는 0, 2

2, 3 입력이 들어오면 둘의 파인드 연산 결과는 0, 3

0, 3 입력이 들어오면 둘의 파인드 연산 결과는 0, 0 이므로 사이클이 완성됐다.

 

소스코드.