P3367 【模板】并查集

P3367 【模板】并查集

---

时间限制 1.00s
内存限制 125.00MB

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数\(N,M\) ,表示共有\(N\)个元素和\(M\)个操作。

接下来\(M\)行，每行包含三个整数\(Z_i,X_i,Y_i\)。

当\(Z_i=1\) 时，将\(X_i\)与\(Y_i\)所在的集合合并。

当\(Z_i=2\)时，输出\(X_i\)与\(Y_i\)是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

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

输入输出样例

输入 #1

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1

N
Y
N
Y

说明/提示

对于\(30\%\)的数据，\(N \le 10\)，\(M \le 20\) 。

对于\(70\%\)的数据，\(N \le 100\)，\(M \le 10^3\)。

对于\(100\%\)的数据，\(1\le N \le 10^4\)，\(1\le M \le 2\times 10^5\) 。

推荐huangzirui的题解 P3367 【【模板】并查集】

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+5;
int f[N];
int find(int x){ return f[x]==x ? x : f[x]=find(f[x]); }
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i) f[i]=i;
	while(m--){
		int z,x,y;
		scanf("%d %d %d",&z,&x,&y);
		int fx=find(f[x]),fy=find(f[y]);
		if(z==1){
			if(fx==fy) continue;
			f[fy]=fx;
		} else {
			if(fx==fy) puts("Y");
			else puts("N");
		}
	}
	return 0;
}