union find的介绍和算法，可以看这篇blog，是基于princeton那本算法红书的：
https://www.cnblogs.com/wxgblogs/p/5707503.html

想看原版的话直接看

https://algs4.cs.princeton.edu/15uf/

里面有java 代码，和复杂度分析。由于我最近在忙面试，没有时间写文字叙述了。下面是我写的union find C++ 版本的代码，其中有path compression 来优化复杂度，让储存数据的树尽量扁平，希望大神看一下，如果我写的不是最优，请指出来，感激不进。（这个题是基于305题，我此题的答案在 https://www.acwing.com/solution/leetcode/content/633/ ）

class UnionFind{
private:
    vector<int> parent;
    vector<int> weight;
    int count;

public:
    UnionFind(int N){
        parent = vector<int> (N, -1);
        weight = vector<int> (N, 0);
        count = 0;
    }

    bool isValid(int i){
        return parent[i] >= 0;
    }

    void SetParent(int i){
        parent[i] = i;
        count++;
    }

    int find(int i){
        if (parent[i]!=i){
            parent[i] = find(parent[i]);
        }

        return parent[i];
    }

    void Union(int x, int y){
        int rootx = find(x);
        int rooty = find(y);

        if (rootx != rooty){
            if (weight[rootx] >= weight[rooty]){
                parent[rooty] = rootx;
                weight[rootx] += weight[rooty];
            }
            else{
                parent[rootx] = rooty;
                weight[rooty] += weight[rootx];
            }
            count--;
        }
    }

    int getCount(){
        return count;
    }

};