P3367 并查集

题目描述

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

输入格式

第一行包含两个整数 $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

样例输入 #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$，$1\le X_i,Y_i\le N$， Z i ∈ { 1 , 2 } Z_i \in \{ 1, 2 \} Zi​∈{1,2}。

solution

#include<iostream>
using namespace std;
const int maxn = 10010;
int f[maxn];//f[i]表示结点i的父节点为f[i] 

int find(int n){
	if(f[n] == n) return n;
	return f[n] = find(f[n]);//路径压缩 ，使树扁平化（胖而非长）
} 

void unionset(int x, int y){
	int f1 = find(x), f2 = find(y);
	if(f1 == f2) return;
	f[find(x)] = find(y);
}

int main(){
	int n, m, x, y, z, f1, f2;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		f[i] = i;//初始化，各自为一个集合 
	}	
	while(m--){
		scanf("%d%d%d", &z, &x, &y);
		if(z == 1) unionset(x, y);
		else{
			f1 = find(x);
			f2 = find(y);
			if(f1 == f2) printf("Y\n");
			else printf("N\n");
		}
	}
	return 0;
}