서로소 집합

서로소 집합(disjoint set) 는 집합의 묶음을 관리하는 자료 구조입니다.

각 집합은 서로소 집합으로, 한 원소가 둘 이상의 집합에 속할 수 없고, 집합에 속한 임의의 원소가 대푯값이 되어 식별할 수 있습니다.

find

find 연산은 각 집합에서 대푯값을 찾을 때 사용합니다.

맨 처음에는 모든 원소는 자신만을 원소로 가지는 집합에 속해있습니다.

이를 나타내기 위해 link와 size 배열을 설정합니다.

// link[i]: i번째 원소가 가리키는 원소. 초기값은 자기 자신을 가리킵니다.
// size[i]: i번째 원소가 속해있는 집합의 크기. 초기값은 1
std::vector<int> link(n + 1), size(n + 1, 1);
std::iota(link.begin(), link.end(), 0);

집합의 대푯값을 구하기 위해서는 집합의 임의의 원소 x에서 시작하는 경로를 따라가면 됩니다.

int find(int x)
{
	// x가 자기 자신을 가리키면 대푯값이다.
	while (x != link[x]) {
		x = link[x];
	}
	return x;
}

경로의 길이가 $O(log n)$이라고 한다면 find 함수의 시간복잡도는 $O(log n)$이 됩니다.

경로 압축

경로 압축(path compression)이라는 방법을 사용하면 더 빠르게 대푯값을 찾을 수 있습니다.

이 연산을 실행하게 되면 집합의 모든 원소가 대푯값을 바로 가리키게 됩니다.

int find(int x)
{
	if (x == link[x]) {
		return x;
	}
	return link[x] = find(link[x]);
}

경로 압축을 사용하게 되면 find 함수는 $O(\alpha(n))$이 됩니다.

$\alpha(n)$은 애커만 함수(Ackermann function)의 역함수로, n이 $10^{80}$ 보다 큰 수에서도 4이하의 값을 나타내므로 사실상 $\alpha(n) \leq 4$가 됩니다.

unite

unite 연산은 두 집합을 합칠 때 사용합니다.

두 집합을 합치기 위해서는 한 집합의 대표값을 다른 집합의 대푯값으로 이으면 됩니다.

이때 작은 크기의 집합의 대푯값이 큰 크기의 집합의 대푯값을 가리키도록 이어서 효율성을 높이도록 합니다.

void unite(int a, int b)
{
	a = find(a);
	b = find(b);
	if (size[a] < size[b]) {
		std::swap(a, b);
	}
	size[a] += size[b];
	link[b] = a;
}