并查集

并查集是一种数据结构，它主要处理一些不相交集合的合并问题。一些常见的用途有求连通子图、最小生成树Kruskal算法和求公共祖先等。

并查集的主要操作有：

1. 初始化Init

2. 查询Find

3. 合并Union

初始化 Init()

void Init(int n) {
    vector<int> father(n + 1);    //创建数组从节点1开始到n
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

查询 Find()

int Find(index,vector<int>& father){
    if(father[index]==index){
    return index;
}                          //递归终点
    else {
    father[index]=Find(father[index],father);
    return father[index];
}                          //记忆化搜索
}                          //查找index的祖先

合并 Union()

void Union(int index1,int index2,vector<int>& father){
    father[Find(index1,father)]=Find(index2,father);
}                         //合并index1和index2的祖先

例题：[冗余连接](. - 力扣（LeetCode）)

class Solution {
public:
int Find(int index,vector<int>& father){
    if(father[index]==index){
        return index;
    }
    else {
        father[index]=Find(father[index],father);
        return father[index];
    }
}//查找index的祖先
void Union(int index1,int index2,vector<int>& father){
    father[Find(index1,father)]=Find(index2,father);
}//合并index1和index2的祖先
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n=edges.size();
        vector<int> father(n+1);
        for(int i=1;i<=n;i++){
            father[i]=i;
        }//初始化节点
        for(auto& edge:edges){
            int node1=edge[0],node2=edge[1];
            if(Find(node1,father)!=Find(node2,father)){
                Union(node1,node2,father);
            }
            else return edge;
        }
        return {};
    }

第一次看这种写法，简直炸裂，学到了：

vector<vector<int>> edges;
for(auto& edge:edges){
    int node1=edge[0],node2=edge[1];
}   //auto& edge 也许是edges中一个向量的索引