1#include <algorithm>
2#include <numeric>
3#include <vector>
4
5class UnionFind {
6 std::vector<std::size_t> root, rank;
7 std::size_t components_;
8
9public:
10 UnionFind(std::size_t size) : root(size), rank(size), components_{size} {
11 std::iota(root.begin(), root.end(), 0);
12 }
13
14 std::size_t find(std::size_t x) {
15 while (x != root[x])
16 x = root[x] = root[root[x]];
17 return x;
18 }
19
20 void merge(std::size_t x, std::size_t y) {
21 auto rx = find(x), ry = find(y);
22 if (rx == ry) return;
23
24 if (rank[rx] > rank[ry]) {
25 std::swap(rx, ry);
26 } else if (rank[rx] == rank[ry]) {
27 ++rank[ry];
28 }
29
30 root[rx] = ry;
31 --components_;
32 }
33
34 std::size_t components() const {
35 return components_;
36 }
37};