并查集算法

对于leetcode 323题目，还有类似的题目。

初始一开始想到的都是DFS， BFS，之类的暴力搜索，可是这样的作法是O(E+V)时间复杂度。
有一个特别好的通用的手法去实现这类，连通分量的问题。

从代码上看, 使用make_unique声明一个UnionFind对象后，只需要针对每个边进行遍历和合并，即可得到整体的连通分量。

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        auto ufind = make_unique<UnionFind>(n);
        for(auto const& edge: edges){
            ufind->unionTwo(edge[0],edge[1]);
        }   
        return ufind->cnt;
    }
};

下面是整个UnionFind类的实现

class UnionFind {
public:
    vector<int> fa;
    vector<int> rank;
    //定制化cnt
    int cnt;
    UnionFind(int n){
        rank.assign(n,1);
        cnt=n;
        for(int i=0;i<n;i++){
            fa.push_back(i);
        }
    }

    //查询x y的父节点，递归查询，当查询
    inline int find(int x){
        if(x==fa[x]) return x;
        return find(fa[x]);
    }

    //当合并的时候，需要对比rank大小，
    inline void unionTwo(int x, int y){
        int fa_x = find(x);
        int fa_y = find(y);
        if(rank[fa_x]<=rank[fa_y]){
            //合并小的到大的
            if(fa_x == fa[fa_x] && fa_x != fa_y){
                cnt--;
            }
            fa[fa_x] = fa_y;

        }else{
            if(fa_y == fa[fa_y] && fa_x != fa_y){
                cnt--;
            }
            fa[fa_y] = fa_x;
        }
        if(rank[fa_x]==rank[fa_y] && fa_x!=fa_y) rank[fa_y]++;
    }
};

实现分析

father数组和rank数组

点1连着点2， 点2连着点3， 那么就是这样 1-2-3
点4连着点5， 点5连着点6， 那么就是这样 4-5-6
father数组的意味就是希望记录每个点的父节点是谁，但是不是直接父节点，而是祖父节点，比如 father(3) = 1, 而非等于2。
所以对于这个案例：

father数组index: (1， 2，3，4，5，6）
father数组value: (1， 1，1，4，4，4）

从这个father数组可以看得出是类似一个树状的，这颗树可以是 1-2-3 这样的，rank此时对于根节点1而言就是3，因为高度为3。
也可以是 1-(2,3), 此时对于根节点1的rank为2，高度为2。当然树的高度越小越好。

合并Union操作

所以对于Union操作，需要找到两个节点的祖父节点，所以又有一个简单的find动作。
找到了两个祖父节点x，y之后，查看rank的大小， 比如知道了x的rank大小为2，比y的rank为1大。
那么可以断定，x就是 1-2 这样的树状结构，y为1那就是单节点，只需要合并进去变成 1-(2,3) 这样的结构就行了。
那么如果是x的rank大小为3，比y的rank为2大呢？合并进去也并不会影响其x的高度。

合并改变rank的情况

只有一种情况会合并的时候改变rank结构，就是两个节点的rank都是一样的，比如都是1，都是单节点，合并后变成 x-y， x的rank变成了2
两个rank节点都是2，x-y, u-v, 合并后，肯定是x - (y,u) - v ， 那么x的rank也是会加1。

find操作

本质上是个递归找到祖父的节点的操作。