[BOJ] 백준 20040 사이클 게임 (Swift)

문제

https://www.acmicpc.net/problem/20040

20040번: 사이클 게임

풀이

유니온 파인드 알고리즘을 활용하여 풀이할 수 있는 문제입니다.

사이클이 완성되는 경우는 어떠한 경우일까요?
현재 1, 2, 3이 다음과 같이 연결되어있다고 가정해봅시다.

현재 2와 3의 부모노드는 1로 같습니다. 2와 3을 연결하면 사이클을 발생시킵니다.
즉, 같은 부모노드를 가진 것 끼리 연결하게 된다면 사이클이 생성되게 됩니다.

그러므로, 연결을 하기 전에 같은 두 노드가 같은 부모노드인지 확인을 하고 같은 부모노드라면 연결을 하게되면 사이클이 발생되므로
그 당시의 차례의 번호를 출력해주면 됩니다.

소스코드

후기

유니온 파인드를 활용한 문제이며, MST를 알고있었다면 쉽게 풀 수 있는 문제였습니다.