유니온파인드 시간복잡도

[baekjoon 20040] 사이클 게임 (유니온 파인드, union-find) (C++)

www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 유니온 파인드를 통해 사이클 판별을 하는 문제이다. 두 개의 정수가 주어지고, 그 둘은 연결되는데 선분들이 연결되다가 사이클이 발생할 때를 출력한다. 사이클이 생성되지 않을 경우 0을 출력. #include using namespace std; int parent[500001], n, m, from, to, answer; int getParent(int x) { if (parent[x] == x) retu..