并查集

一 ，并查集的构造

① 设定一个集合，叫并查集，即 Disjoint Set，功能是检查 图中 是否出现了 环
② 往集合里面添加边，怎么添加呢。取边的起点和终点，判断两点是否都在集合里面，如果都在，则出现了环，如果不在，将两个点 放入集合中。
③ 继续添加下一条边，如果没有边了，还没有找到环，就是没有环了

二，数组以树的形式实现

上面所讲的就是基本的思想了，下面讲如何具体实现

① 由于集合操作并不方便，所以便设法使用数组实现

② 由于上面所说的添加边 可以看成是一组点的集合 连接 另外一组点的集合，所以我们只要随便让集合的某一点 连接 另外一个集合的任意一点 就行了
这样就可以让所有点处于连通状态

③ 基于上述所讲，我们可以将点以树的形式连接，为什么是树呢？因为集合中没有环，所以最后画出来的图形就是树了。

④ 由于连接的随意性， 这种连接方式，并不能正确表示一张图，只是能表示所有点是连接在一起的，且这种图画出来是树的形式。

⑤ 所以，我们可以构造一个 parent 数组，什么意思呢 ？ 就是 parent[x]=y, 指 x 的父节点是 y ,

为什么要 定义一个父节点呢？ 定义父节点的意思是 你可以通过父节点找到这个集合的根 ，根就是 所有点 都由 这个点 出发得到的。

那么，为什么要找到这个根呢？ 即这样做的优点。
优点1，在添加边的时候，可以通过查找 边上两个点的根结点是否存在，是否相同，达到判断两个点是否在之前的集合中出现过的效果
优点2，可以在 加边 时减少树的深度，之后查找 根节点时就可以减少步骤

三，压缩路径

且看我上面优点 2 这一句 “但如果让 3 的父节点为 0 深度增加了一层” ，其实如果但如果让 0 的父节点为 3 深度就没有增加了

之前的代码中，我们这一步那个时那个的父节点我们并没有对此做一个判断，来判断哪一个成为 父节点 树的深度会更少。
这样子就有一个问题，如果一直是
0-1 1-2 2-3 3-4 这样子就会让树的深度一直增加，这样就会让 find_root 函数时间复杂度在最坏的情况下达到 o(n) ,即每个点都要查找。
所以，我们使用 rank 数组来记录 树的深度，如 rank[x]=y 表示 以 x 点为根结点的话，树的深度为 y
题目：
https://www.luogu.com.cn/problem/P1551

#include<iostream>
using namespace std;
int a[5001],rank[5001];
int n,m,p;
//n个人，m个亲戚关系，询问p对亲戚关系 
//寻找该点的最最最原始的结点，直到找到没有父节点的0为止 
int find_root(int x,int a[]){
    //先将根节点设为自己 
    int x_root = x;
    //往上找，如果不是0就继续 
    while(a[x_root]){
        x_root = a[x_root];
    }
    //返回根节点 
    return x_root;
}
//合并 
int union_vertices(int x,int y,int a[],int rank[]){
    //找到x和y的根节点 
    int x_root = find_root(x,a);
    int y_root = find_root(y,a);
    //如果相同就不用并了，是一家人 
    if(x_root == y_root){
        return 0;
    }else{
        //a[x_root]=y_root;
        //如果x的层数比y的层数高，就把y并到x上，总层数不变 
        if(rank[x_root] > rank[y_root]){
            a[y_root] = x_root;
        }else if(rank[y_root] > rank[x_root]){
            a[x_root] = y_root;
        }else{//如果层数相同，就随便并一下，层数加一 
            a[x_root] = y_root;
            rank[y_root]++; 
        }   
        return 1;
    }   
}

int main(){
    cin>>n>>m>>p;
    while(m--){
        int x,y;
        cin>>x>>y;
        union_vertices(x,y,a,rank);
    }
    while(p--){
        int x,y;
        cin>>x>>y;
        int x_root = find_root(x,a);
        int y_root = find_root(y,a);
        if(x_root == y_root){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

链接：
https://www.cnblogs.com/asdfknjhu/p/12515480.html
https://www.bilibili.com/video/BV13t411v7Fs