首页 > 代码库 > 并查集【模板】
并查集【模板】
https://www.luogu.org/problem/show?pid=3367#sub
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。
输入输出格式
输入格式：
第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi
当Zi=1时，将Xi与Yi所在的集合合并
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N
输出格式：
如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N
输入输出样例
输入样例#1：
4 72 1 21 1 22 1 21 3 42 1 41 2 32 1 4
输出样例#1：
NYNY
说明
时空限制：1000ms,
数据规模： 128M
#include <iostream>#include <cstdio>using namespace std;int n,m,x,y,z;int fa[1000015];int find(int x){ if(fa[x]!=x) return fa[x]=find(fa[x]); return x;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d%d",&z,&x,&y); if(z==1) fa[find(x)]=find(y); if(z==2) if(find(x)==find(y)) cout<<"Y"<<endl; else cout<<"N"<<endl; } return 0;}
并查集【模板】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。