유니온-파인드 자료구조(C/C++ 구현, 시간복잡도)

1. 정의

컴퓨터 과학 분야 에서 서로소 집합(disjoint-set) 자료 구조, 또는 합집합-찾기(union–find) 자료 구조, 병합-찾기 집합(merge–find set)은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. 

출처 : 위키피디아

 

내 해석 :  묶음으로 되어있지 않은 집합을 찾아내는 것, 사이클이 없음

한 노드의 부모를 찾거나 두 노드가 한 집합이 되도록 합치거나.

 

2. 구현

1) find(x) : x의 부모를 찾는 함수

 - 경로 압축 : 시간 복잡도 상수 복잡도를 가진다고 함.

 

2) Union(a,b) : a와 b를 연결하는 함수(한 쪽으로 연결시켜줌)

 - 한 쪽으로 연결 시켜주는것이 헷갈리지 않음 ( 작은 쪽 or 큰 쪽)

 

3. 시간 복잡도

1) Find : 상수복잡도

아크만 함수로 그렇다고 함

아크만 함수의 시간 증가율은 상수복잡도를 가진다고 함....

2) Union : O(logn) 경로의 길이가 O(logn)인 기준

두개의 부모를 찾개되면 트리의 높이는 최대 2로 오르게 되므로 log 시간 복잡도를 가짐

 

//원래 자기 자신이 부모. 연결되면서 부모를 정함
void init()
{
	for (int i = 1; i <= n; i++)
	parent[i] = i;
}
//부모를 찾는 함수 (이렇게 구하는걸 경로 압축이라고 한다)
//모든 경로가 부모를 가르키게 함
//상수 시간의 복잡도를 가짐
int Find(int x)
{
	if (parent[x] == x) return x;
	return parent[x] = Find(parent[x]);
}
//두 노드를 연결 시키는 것
//기준을 정해서 연결시키는 것이 헷갈리지 않음
//작은쪽이 부모 or 큰쪽이 부모
void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
	if (x != y)
	{
		if (x < y)
			parent[y] = x;
		else
			parent[x] = y;
	}
}