并查集（Union-find Data Structure）是一种树型的数据结构。它的特点是由子结点找到父亲结点，用于处理一些不交集（Disjoint Sets）的合并及查询问题。
- Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- Union：将两个子集合并成同一个集合
关于并查集是什么我们在这里不作详细讲解，我们直接学习其中操作，如果你对并查集不了解，请自行去查找
一.合并：
我们将两个集合合并在一起模版：
//并查集:
const int N = 1e3;
int fa[N], sz[N], dep[N];
int findset(int x)
{if (x == fa[x])return x;elsereturn findset(fa[x]);
}
void Union(int x, int y)
{int fx = findset(x), fy =findset(y);if (fx == fy)return;elsefa[fx] = fy;//我们这里默认将fx合并到fy
}二.路径压缩：
我们可以将一个长链压缩成右图：
好处：可以大大减少合并次数
模版：
//路径压缩;
int findset(int x)
{if (fa[x] == x)return x;fa[x] = findset(fa[x]);return fa[x];
}//简写
int findset2(int x)
{return x == fa[x] ? x : (fa[x] == findset2(fa[x]));
}三.按size合并
模版：
const int N = 1e3;
int fa[N], sz[N], dep[N];
//启发式合并;
//size合并;
void Union(int x, int y)
{int fx = fa[x], fy = fa[y];if (fx == fy)return;if (sz[fx] > sz[fy])//默认是将fx合并到fy，所以我们如果size：fx>fy，可以交换fx fy，这样和默认就一样了swap(fx, fy);fa[fx] = fy;//默认是将fx合并到fysz[fy] += sz[fx];//fx合并到fy后，fy上元素个数会增加sz[fx]个
}四.按深度合并：
//按深度合并
void Union(int x, int y)
{int fx = fa[x], fy = fa[y];if (fx == fy)return;if (dep[fx] > dep[fy])swap(fx, fy);fa[fx] = fy;if (dep[fx] == dep[fy])//注意：只有两个深度相同时，合并总深度才会增大dep[fy]++;
}以上就是我们关于并查集的模版
你学会了吗？现在通过这题来测试下吧：
【模板】并查集 - 洛谷
我的解答：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,z,x,y;
int fa[N];int findset(int x)
{if(fa[x]==x)return x;fa[x]=findset(fa[x]);return fa[x];
}int main()
{//取消同步流ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//输入cin>>n>>m;//构造并查集for(int i=1;i<=n;i++){fa[i]=i;}for(int i=1;i<=m;i++){cin>>z>>x>>y;if(z==1)//合并操作{int fx=findset(x),fy=findset(y);if(fx==fy)continue;elsefa[fx]=fy;}else//查询操作{int fx=findset(x),fy=findset(y);if(fx==fy)cout<<'Y'<<endl;elsecout<<'N'<<endl;}}return 0;}下面给一道练习题：
亲戚 - 洛谷
#include <bits/stdc++.h>
using namespace std;
const int N=1e4;
int a[N];int findset(int x)
{if(a[x]==x)return x;a[x]=findset(a[x]);return a[x];
}int main()
{int n,m,p;scanf("%d%d%d",&n,&m,&p);for(int i=1;i<=n;i++)a[i]=i;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);//并查集int fx=findset(x),fy=findset(y);if(fx==fy)continue;elsea[fx]=fy;}for(int i=1;i<=p;i++){int x,y;scanf("%d%d",&x,&y);//并查集int fx=findset(x),fy=findset(y);if(fx==fy)printf("Yes\n");elseprintf("No\n");}return 0;
}最后，感谢大家的支持！！！
