【模板】并查集
题目传送门
题目描述
如题,现在有一个并查集,你需要完成合并和查询操作。
输入格式
第一行包含两个整数 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;
}