+C++20
C++20판은 원소 번호를 size_t로 저장한다. 메서드에 넘기는 번호는 생성한 count개의 원소 범위 안에 있어야 한다. union은 C++ 예약어이므로 병합 메서드 이름을 unite로 쓰고, 크기가 같으면 TypeScript판처럼 첫 인자의 루트를 유지한다.
#include <cstddef>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
class UnionFind {
std::vector<std::size_t> parent;
std::vector<std::size_t> sizes;
public:
explicit UnionFind(std::size_t count) : parent(count), sizes(count, 1) {
std::iota(parent.begin(), parent.end(), std::size_t{0});
}
std::size_t find(std::size_t value) {
auto root = value;
while (root != parent[root]) root = parent[root];
while (value != root) {
const auto next = parent[value];
// 검색한 경로의 노드들을 루트 바로 아래에 연결한다.
parent[value] = root;
value = next;
}
return root;
}
bool unite(std::size_t a, std::size_t b) {
auto rootA = find(a);
auto 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(std::size_t value) {
return sizes[find(value)];
}
};
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
TypeScript