Disjoint Sets

n개의 원소를 하나의 자료구조로 합쳐 조작하고 탐색하기 용이하게 만드는 자료구조

n개의 원소가 n개의 set으로 초기화됨 (MakeSet())

Tree를 사용하는 것이 효율적.

Tree의 구현은 각 node의 parents를 저장하는 배열로 (parents[i] = j)

Union() -> 두 set을 하나의 set으로 합치는 작업 (O(n))

void simpleUnion(int i, int j)
{parent[i] = j;}

효율적인 union을 위해 set의 height정보도 같이 저장하고 union시 높이가 낮은 set을 높이가 큰 set에 붙여서 합침

두 set의 height가 같으면 union된 set의 height 증가

 

Find() -> 어떤 set안에 특정 element가 들어있나 찾음(포함된 set의 root를 반환) (O(nlogn) 평균  O(n-1))

int simpleFind(int i)
{
	while (parent[i] >= 0)
	i = parent[i]; // move up the tree
	return i;
}

Find시 최종적으로 찾아진 root를 자신의 부모로 만들어 경로를 압축할 수 있음 (path compression)

int Find(int i)
{
	return parents[i] = Find(parents[i])
}

Kruskal 알고리즘 구현 시 사용됨

참고