P3367 【模板】并查集 - 洛谷

题目背景

复制 Markdown​
**[提交]**​
进入 IDE 模式

自2025年1月21日，本题测试数据范围更新，详见: https://www.luogu.com.cn/discuss/1045596
这意味现存题解的代码可能无法通过本题，管理组将会在2025年2月处理。

题目描述

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

输入格式

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

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

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

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

输出格式

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

输入输出样例

输入 #1

markdown

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

输出 #1

markdown

N
Y
N
Y

说明/提示

• 对于 15% 的数据，N≤10，M≤20。
• 对于 35% 的数据，N≤100，M≤1e3。
• 对于 50% 的数据，1≤N≤104，1≤M≤2×1e5。
• 对于 100% 的数据，1≤N≤2×105，1≤M≤1e6，1≤Xi​,Yi​≤N，Zi​∈{1,2}。

思路：

就是模板，没什么思路

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std; 
const int N = 2e5+10;
int fa[N];
int find(int i)
{
	if(fa[i] != i)
	{
		fa[i] = find(fa[i]);
	}
	return fa[i];
}
void set(int u,int v)
{
	int u1 = find(u);
	int v1 = find(v);
	if(u1 != v1)
	{
		fa[v1] = u1;
	}
}
bool check(int u,int v)
{
	return find(u) == find(v);
}
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i = 1 ; i <= N ; i++)
	fa[i] = i;	
	for(int i = 1 ; i <= m ; i++)
	{
		int z,x,y;
		cin >> z >> x >> y;
		if(z == 1)
		{
			set(x,y);
		}
		else if(z == 2)
		{
			if(check(x,y))
			{
				cout << 'Y' << '\n';
			}
			else
			{
				cout <<'N' << '\n';
			}
		}
		
	}
	
    return 0;
}