+C++20
The C++20 version stores element indices in size_t. Method arguments must be within the count elements created by the constructor. Since union is a C++ keyword, the merge method is named unite; a size tie keeps the first argument’s root, just as in 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];
// Point each node on the traversed path directly at the root.
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