Union Find ：解决集合 合并O(1)、查找O(1)

原生操作：

• 查询量元素是否在同一集合
• 合并两元素所在集合

派生操作：

• 查询某个元素所在集合的元素个数
• 查询当前集合个数

模板：

class UnionFind {
public:
    UnionFind(int n) {
        father = vector<int>(n, 0);  // father为自己表示为0
    }
    int find(int x) {
        if (father[x] == 0) {  
            return x;
        }
        return father[x] = find(father[x])；  // compressed unionfind压缩路径
    }

    void union(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);
        if （root_a != root_b) {
            father[root_a] = root_b;  // union一定是在能代表整个集合的“老大哥”节点进行，而不是ab本身，
        }                             // 这样才能代表整个集合的合并
    }

    bool inTheSameUnion(int a, int b) {  // 通过判断“老大哥”是否相等来判断是否在同一集合
        return find(a) == find(b);       // 不能直接用father[]判断，因为要通过find压缩路径才能得到最新的“老大哥”
    }

private:
    vector<int> father;
}