【模板】并查集

题目传送门
题目描述
如题,现在有一个并查集,你需要完成合并和查询操作。

输入格式
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来M 行,每行包含三个整数Zi,Xi,Yi。

当Zi=1 时,将Xi与Yi所在的集合合并。

当Zi=2 时,输出Xi与Yi是否在同一集合内,是的输出 Y ;否则输出 N 。

输出格式
对于每一个Zi=2 的操作,都有一行输出,每行包含一个大写字母,为 Y 或者 N 。

输入输出样例
输入
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出
N
Y
N
Y
说明/提示
对于30% 的数据,N≤10,M≤20。

对于 70% 的数据,N≤100,M≤103

对于100% 的数据,1≤N≤104,1≤M≤2×104
正解

做了这么多到并查集的题目了
应该还有人不知道并查集什么吧
现在,我来讲讲并查集是什么

并查集
就是合并
就是查找
就是集合
总而言之:合并集合,查找集合
为了方便将两个数字的集合合并
为了方便判断两个数字是否属于同一集合

就有了并查集

这道题,就是一个并查集模板大家要学好并查集,以后有大作用哦
AC代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,z,x,y,pre[10005];
int find(int x)//找爸爸+路径压缩
{
   
	if(pre[x]==0)return x;
	return pre[x]=find(pre[x]);
}
void bcj(int x,int y)//并查集
{
   
	int x1=find(x),y1=find(y);//找爸爸
	if(x1!=y1)pre[y1]=x1;//合并
}
int main()
{
   
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
   
		cin>>z>>x>>y;
		if(z==1)bcj(x,y);//如果z==1就合并集合,否则就判断集合是否一样
		else if(find(x)==find(y))cout<<"Y"<<endl;
			  else cout<<"N"<<endl;
	}
	return 0;
}

谢谢观看