Disjoint-set algorithm (union-find)

Disjoint-set algorithm은 말 그대로 집합과 관련된 알고리즘을 일컫는다. 예를 들어 집합 A = {1, 2, 3}와 B = {6, 7, 8}에 대해서

원소 6과 8이 같은 집합에 있는가?와 같은 대답을 할 수 있어야하며, (find)

집합 A와 집합 B를 합칠 수 있어야 한다. (union)

방법은 생각보다 간단하다.

일종의 Tree를 그려놓는 것으로 집합을 대신할 수 있다.

예를 들어 집합 A = {1, 2, 3}에 대해서

1 <- 2 <- 3 과 같은 Tree를 그릴 수 있다.

이런 트리는 역으로 생각해보면,

parent(1) = 1, parent(2) = 1, parent(3) = 2와 같이 parent 정보를 이용해서 구할 수 있다.

이는 메모이제이션 기법을 이용하면 최적화 할 수 있다.

int p[1000001];
int parent(int x)
{
	if (p[x] == x){
		return p[x];
	}
	return p[x] = parent(p[x]);
}

그렇다면, Tree의 union은 어떻게 해야할까?

단순히 생각해보면

집합 A : 1 <- 2 <- 3

집합 B : 4 <- 5 <- 6

에 대해서 parent[root[B]]에 root[A]를 넣으면 될 것이다.

즉, parent[4] = 1을 넣으면 만사 ok이다. (물론 그 반대도 가능)

그런데 문제는 집합 A : 1 <- 2 <- 3이고,

집합 B가 4 <- 5 <- 6 <- ... <- 105 라고 가정해보자

n(B)가 n(A)보다 압도적으로 큰 경우에, 부분 집합 B의 parent를 구할 때 모두 다 갱신을 해줘야하므로 매우 비효율적인 것을 알 수 있다.

그렇기 때문에 집합을 합칠때 집합 A의 크기와 집합 B의 크기를 미리 고려하여 합칠 경우 시간 단축을 진행할 수 있다.

int rn[1000001];
void addTree(int a, int b) {
	int pA = parent(a);
	int pB = parent(b);
	if (pA == pB) {
		return;
	}
	
	if (rn[pA] >= rn[pB]) {
		p[pB] = pA;
		rn[pA] += rn[pB];
	}
	else {
		p[pA] = pB;
		rn[pB] += rn[pA];
	}
}

위와 같이 rank를 미리 1로 초기화해놓고 rank를 비교하는 식으로 알고리즘을 짤 경우 시간 단축에 매우 도움이 된다.

BOJ 1717 집합의 표현 문제에 대한 코드가 아래와 같다.

#include <iostream>
#include <stdio.h>
using namespace std;
int n, m;
int p[1000001];
int rn[1000001];

int parent(int x)
{
	if (p[x] == x){
		return p[x];
	}
	return p[x] = parent(p[x]);
}

bool equalParent(int a, int b){
	return parent(a) == parent(b);
}

void addTree(int a, int b) {
	int pA = parent(a);
	int pB = parent(b);
	if (pA == pB) {
		return;
	}
	
	if (rn[pA] >= rn[pB]) {
		p[pB] = pA;
		rn[pA] += rn[pB];
	}
	else {
		p[pA] = pB;
		rn[pB] += rn[pA];
	}
}


int main() {
	int a, x, y;
	scanf("%d%d", &n, &m);
	for(int i=0; i<=n; i++) {
		rn[i] = 1;
		p[i] = i;
	}
	
	while(m--) {
		scanf("%d%d%d", &a, &x, &y);
		if(a) {
			printf("%s", equalParent(x,y) ? "YES\n" : "NO\n");
		}
		else {
			addTree(x, y);
		}
	}
	
	return 0;
}