题目选自洛谷P3367

是并查集的最入门的题目，也是并查集的模板题~~

如果你还不知道并查集是什么？ 请看我的这篇文章 点击链接

 

题目描述

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

输入格式

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

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

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

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

输出格式

对于每一个 Zi​=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≤10，M≤20。

对于70% 的数据，N≤100，M≤10^3。

对于 100% 的数据，1≤N≤10^4，1≤M≤2×10^5，1≤Xi​,Yi​≤N，Zi​∈{1,2}。

解题代码：

#include<stdio.h>
#include<iostream>
using namespace std;
int n,m,opt,x,y,f[10001];
void init(){
	for(int i=1;i<=n;i++) f[i] = i;
}
int find(int x){
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}
void merge(int x,int y){
	if(find(x) != find(y))
		f[find(x)] = find(y);
}
int main(){
	cin>>n>>m;
	init();
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&opt,&x,&y);
		if(opt == 1){
			merge(x,y);
		}else{
			if(find(x) == find(y)) printf("Y\n");
			else printf("N\n");
		}
	}
	return 0;
}