写在这方便以后参考

Implementation

class UnionSet {
private:
    vector<int> pa;
    vector<int> size;
public:
    UnionSet(int n) {
        pa.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++) {
            pa[i] = i;
        }
    }

    int recursive_find(int x) {
        return pa[x] == x ? x : pa[x] = recursive_find(pa[x]);
    }

    int find(int x) {
        int r = x;
        while (pa[r] != r) r = pa[r];
        while (pa[x] != r) {
            int p = pa[x];
            pa[x] = r;
            x = p;
        }
        return r;
    }

    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (size[x] < size[y]) {
                swap(x, y);
            }
            pa[y] = x;
            size[x] += size[y];
        }
    }

    int getSize(int x) {
        return size[find(x)];
    }
};