转载请注明来源：https://www.cnblogs.com/TheSilverMoon/p/9309481.html

并查集简单点说就是判断图的两个点是否连通，但是一个个查找很麻烦，怎么办呢？那就让他们的老大直辖所有的小弟，所以我们每次查询只要看他们俩的老大是不是一样的就可以了。

下面是我的并查集代码

同时推荐一个大佬的解释，很有意思https://blog.csdn.net/u013546077/article/details/64509038

#include 
     
      #define fi first#define se second#define pb push_back#define fio ios::sync_with_stdio(false);cin.tie(0);#define pii pair
      
       #define vi vector
       
        #define vc vector
        
         #define pi 3.1415926const int INF=0x3f3f3f3f;const int N=1e5+5;typedef long long ll;typedef double db;typedef unsigned long long ull;using namespace std;int pre[N];//记录各个点的上一个节点，如果自己是老大就等于自己int findRoot(int n)//查找根节点{    int r=n;    while(pre[r]!=r)//查找这个点的根节点    {        r=pre[r];    }    //r现在是根节点    int i=n,j;    while(i!=r)//路径压缩，让小弟直接归老大直辖    {        j=pre[i];        pre[i]=r;        i=j;    }    return r;}void join(int x,int y)//把各个连同分支连起来{    int r1=findRoot(x);    int r2=findRoot(y);    if(r1!=r2)//如果已经连通不用管    {        pre[r1]=r2;//不连通的时候随便指定一个是另一个的老大    }}int main(){}