Union Find (=disjoint set)

필요한 것: uf배열.

find 함수 :

 1. uf 배열이 -1로 초기화된 경우

 2. uf 배열이자기자신으로 초기화된 경우

merge 함수:

 1. merge함수가 일반적으로 union의 기능만을 수행하는 경우

 2. MST등에서 union에 성공했을 떄 true, 실패했을 때 false 반환하는 경우

 3. merge 후 대표정점(집합)에 포함된 요소의 크기를 초기화해주는 경우

등등등.. 상황에 맞게 구현할 수 있다

 

<1>

int uf[MAX];

//uf배열이 -1로 초기화된 경우
int find(int a) {
	if (uf[a] == -1) return a;
	return uf[a] = find(uf[a]);
}

//union기능만 수행
void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	uf[a] = b;
}

 

<2>

int uf[MAX];

//uf배열이 자기 자신으로 초기화된 경우
int find(int a) {
	if (uf[a] == a) return a;
	return uf[a] = find(uf[a]);
}

//union기능외에 실패/성공여부 반환
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	uf[a] = b;
	return true;
}

 

<3>

int uf[MAX], num[MAX];
int find(int u) {
	if (uf[u] == -1) return u;
	return uf[u] = find(uf[u]);
}

int merge(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return num[v];
	uf[u] = v;
	num[v] += num[u];
	num[u] = 1;
	return num[v];
}

어떤 정점이 포함된 집합에 몇개의 요소가있는지 

-> num[find(u)]

 

---

위와 같이 uf[u] = find(uf[u])처럼 시간복잡도를 줄이는 것을 경로압축이라고 하는데, '동적 연결성 확인 알고리즘'에선 이 로직을 적용하지 못한다. 

 

경로압축을 하지 않고 find,merge의 시간복잡도를 log시간으로 줄이려면, merge함수에서 집합의 크기가 작은 것을 집합의 크기가 큰 곳에 붙이면 된다.