유니온 파인드(Union-Find) 자료구조를 사용해서 상호 배타적 집합을 표현한다. 유니온 파인드란, 공통 원소가 없는, 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 있는 자료구조이다. 이는 아래와 같은 연산을 수행한다.

• 초기화 : 각 원소마다 집합에 포함되어 있도록 초기화한다.
• 합치기 연산 : 두 원소가 속한 두 집합을 하나로 합친다.
• 찾기 연산 : 원소 하나가 속해있는 집합을 찾아 반환한다.

이는 배열 하나로 표현되는데, belongsTo[i]는 i번 원소가 속하는 집합의 번호이다.

이때 합치기 연산은 O(N)에 시행된다. 이 연산을 빠르게 하기 위해서, 한 집합에 속하는 원소들을 트리 자료구조로 저장한다. 같은 루트를 가지고 있는 원소라면 같은 집합에 속하는 것이다. 루트는 부모가 없으므로 자기 자신을 가리키고, 자식 노드에 대한 정보는 따로 저장하지 않는다.

struct NaiveDisjointSet {
	vector<int> parent; 
	NaiveDisjointSet(int n) : parent(n) {
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}

	// u가 속한 트리의 루트 번호를 반환한다.
	int find(int u) const {
		if (u == parent[u]) return u;
		return find(parent[u]);
	}

	// u와 v의 트리를 합친다.
	void merge(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return;
		parent[u] = v; 
	}
};

간단하게 구현한 상호배타적 집합이다.

이를 아래 두가지 방법으로 최적화할 수 있다.

(1) 합치기 연산에서의 최적화

낮은 트리를 높은 트리에 합치는 방식으로 해야 트리가 기울여지지 않고 높이가 최소인 트리를 만들 수 있다.

트리의 높이는 각 원소가 속한 트리의 높이가 같을 때만 1씩 증가한다. 높이가 h인 트리를 만들려면 h-1의 높이를 가진 트리들을 합쳐야 한다. h-1 높이의 트리에는 최소 x개의 원소가 있다고 했을 때, 합쳐진 h 높이의 트리는 2x 개의 원소가 있을 것이다. 같은 방식으로 h + 1 높이의 트리에는 4x가 있을 것이므로, 합치기 연산은 O(logN) 시간복잡도를 가지게 된다.

(2) 찾기 연산의 최적화

경로 압축 최적화를 사용했다. 기존에 찾기 연산이 중복되어 수행되고 있었는데, parent[u] 를 찾아낸 루트로 바꾸게 된다면 재귀호출에 따라 값이 순차적으로 저장되어 다음 번에 find(u)가 호출되었을 때 O(1)로 루트의 번호를 계산할 수 있다.

struct OptimizedDisjointSet {
	vector<int> parent, rank; 
	OptimizedDisjointSet(int n) : parent(n), rank(n - 1) {
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}

	// u가 속한 트리의 루트 번호를 반환한다.
	int find(int u) const {
		if (u == parent[u]) return u;
		return parent[u] = find(parent[u]);
	}

	// u와 v의 트리를 합친다. 이때 v가 u보다 더 높은 트리에 속함을 전제한다.
	void merge(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return;
		if (rank[u] > rank[v]) swap(u, v);
		// v는 항상 u의 위에 있으므로, v를 u의 부모 노드로 넣는다.
		parent[u] = v; 
		if (rank[u] == rank[v]) rank[v]++; 
	}
};