题解 | #并查集的实现#

1. 初始化：自己指向自己
2. 合并：合并操作都发生在根上
3. 判连通：父节点相同，则连通

class UnionFind {
    vector<int> pre;
public:
    UnionFind(int n) {
        pre.resize(n);
        for(int i = 0; i < n; i++)
            pre[i] = i;
    }
    int root(int x) {
        return pre[x] = (x == pre[x]) ? x : root(pre[x]);
    }

    void union_(int a, int b) {
        pre[root(a)] = root(b);
    }

    bool find_(int a, int b) {
        return root(a) == root(b);
    }
};