+C++ example
Because union is a reserved keyword in C++, the merge method is named unite, and std::iota initializes the parent array to $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];
// Point every traversed node directly at the root (path compression).
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;
// Attach the smaller tree under the larger tree’s root to bound height.
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;
}
Output:
true
false
false
4