+C++ 예제
C++에서는 union이 언어 예약어(공용체 키워드)이므로 메서드 이름을 unite로 짓고, std::iota로 초기 부모 배열을 $0, 1, \dots, n-1$로 채운다.
#include <cstddef>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
class UnionFind {
public:
explicit UnionFind(std::size_t count) : parent_(count), sizes_(count, 1) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int value) {
int root = value;
while (root != parent_[root]) root = parent_[root];
while (value != root) {
int next = parent_[value];
// 루트를 찾으며 지나온 모든 노드를 루트 직속 자식으로 물린다(경로 압축).
parent_[value] = root;
value = next;
}
return root;
}
bool unite(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) return false;
// 원소 수가 적은 트리를 큰 트리 루트 밑에 붙여 높이 증가를 억제한다.
if (sizes_[rootA] < sizes_[rootB]) std::swap(rootA, rootB);
parent_[rootB] = rootA;
sizes_[rootA] += sizes_[rootB];
return true;
}
std::size_t sizeOf(int value) { return sizes_[find(value)]; }
private:
std::vector<int> parent_;
std::vector<std::size_t> sizes_;
};
int main() {
UnionFind groups(5);
groups.unite(0, 1);
groups.unite(2, 3);
groups.unite(1, 2);
std::cout << std::boolalpha;
std::cout << (groups.find(0) == groups.find(3)) << '\n';
std::cout << (groups.find(0) == groups.find(4)) << '\n';
std::cout << groups.unite(0, 3) << '\n';
std::cout << groups.sizeOf(3) << '\n';
return 0;
}
실행 결과:
true
false
false
4