유니온 파인드(Union find)

유니온 파인드에는 크게 두가지의 최적화 기법이 있는데 하나는 Union by rank라는 방식이고, 나머지는 경로 압축(path compression)라는 방식이다.

 

상황에 맞게 골라서 최적화 하면 되는데 구현이 쉽기때문에 주로 경로 압축 방식을 주로 사용한다.

 

다음은 경로 압축(path compression)을 통해 최적화 된 Disjoint set의 코드이다

int find(int num) {
	if (parent[num] == num) return num;
	else return parent[num] = find(parent[num]);
}
void uni(int a, int b) {
	if (find(a) != find(b)) parent[find(b)] = find(a);
}
//main 안에:
//for (int i = 0; i < n; i++) parent[i] = i;

참고하면 좋은 글이다: 

https://gall.dcinside.com/mgallery/board/view/?id=ps&no=7207&page=1

유니온 파인드 - PS 갤러리