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

www.acmicpc.net/problem/20040

20040번: 사이클 게임

유니온 파인드를 통해 사이클 판별을 하는 문제이다.

 

두 개의 정수가 주어지고, 그 둘은 연결되는데 선분들이 연결되다가 사이클이 발생할 때를 출력한다.

사이클이 생성되지 않을 경우 0을 출력.

 

#include <iostream>

using namespace std;

int parent[500001], n, m, from, to, answer;

int getParent(int x) {
	if (parent[x] == x)
		return x;
	else
		return parent[x] = getParent(parent[x]);
}

bool unionParent(int x, int y) {
	x = getParent(x);
	y = getParent(y);

	if (x == y)
		return true;
	else {
		if (x > y) {
			parent[x] = y;
		}
		else
			parent[y] = x;
	}
	return false;
}


int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}
	for (int i = 0;  i < m; i++) {
		cin >> from >> to;
		if (unionParent(from, to) && answer == 0)
			answer = i + 1;
	}

	cout << answer;
}

유니온 함수를 약간 수정해서 합치기 전에 그 둘의 parent가 같다면 사이클이 생성된 경우이므로 true를 반환해주고, 아니면 합쳐주고 false를 반환하여 진행하였다.

 

ex)

6 5

parent 배열

0	1	2	3	4	5
0	1	2	3	4	5

0 1 (각각 0 하고 1이기 때문에 false 반환 후 parent 배열 update)

0	1	2	3	4	5
0	0	2	3	4	5

1 2 (각각 0 하고 2이기 때문에 false 반환 후 update)

0	1	2	3	4	5
0	0	0	3	4	5

1 3 (각각 0 하고 3이기에 false 반환)

0	1	2	3	4	5
0	0	0	0	4	5

0 3 (0과 0으로 cycle이 생성 -> true 반환)

4 5

 

union-find의 시간 복잡도

 

 유니온 파인드는 트리를 생성한다.

그리고 find함수는 재귀적으로 부모 노드가 루트 노드를 반환한다. 트리의 구조 상 최상위 노드는 루트로 자기 자신을 가리키고 있기 때문에 종료된다.

하지만 트리가 한쪽으로 치우친 경우, 매번 노드의 최상위 부모 노드를 찾기 위해서는 O(n)이 필요하다.

이 때문에 경로 압축을 사용한다. (트리의 높이를 줄여준다.)

즉, 루트 노드까지 도달 후 그 루트 노드 값을 가지고 내려오면서 자식 노드들의 부모를 루트 노드로 업데이트해준다.

 

따라서, find와 union 함수는 find의 시간 복잡도와 연결되어 있으며, 트리가 한쪽으로 치우쳤다면 O(n)이 소요된다.

하지만 경로 압축을 통해 O(a(n))이 되고, α(x)는 애커만 함수라고 하는데 x가 2의^65536일 때 함숫값이 5가 된다.

따라서, 그냥 O(1)이라고 생각해도 좋다고 한다.