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};