集合问题(并查集)

原创已于 2024-02-01 23:40:54 修改 · 粉丝可见 · 634 阅读 · 3 · 9 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135983545

本题链接：登录—专业IT笔试面试备考平台_牛客网

题目：

样例1：

`cobol<br/>4 5 9<br/>2 3 4 5<br/>`

YES 0 0 1 1

样例2：

`cobol<br/>3 3 4<br/>1 2 4<br/>`

NO

思路：

这道题关键点在于。

当集合中有一个元素均存在于集合 A 和集合 B 的时候是 NO。

并且 $$
P_{i}
$$的范围是 1 ~ 1e9 所以，当 $$
P_{i}
$$>= max(a,b) 的时候也是 NO。

我们同时可以指定一个元素范围外的一个元素作为根元素集合 A，B

其次，我们可以将下标作为对应的每一个元素，最后进行合并求结果即可。

代码详解如下：

#include <iostream>
#include <vector>
#include <unordered_map>
#define umap unordered_map
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
 
umap<int,int>pos;	// 存储元素对应的下标
 
// 存储元素集合,至于为什么也用 umap ,由于 Pi 的数据范围上限是 1e9
// 我们要将数组无法开辟这么大，所以我们只能弄个映射 来存储对应的 A，B 根元素
umap<int,int>father;	
 
// 并查集查找函数
inline int Finds(int x)
{
	int t = x;	// 记录其实查找结点
	while(x != father[x]) x = father[x];	// 开始查找
	father[t] = x;	// 路径压缩查找
	return x;	// 返回结果
}
 
// 并查集合并操作
inline void Union(int a,int b)
{
	a = Finds(a),b = Finds(b);	// 查找对应根节点
	father[a] = b;	// 合并对应根节点
}
 
inline void solve()
{
	int n,a,b;
	cin >> n >> a >> b;
	int maxs = max(a,b);	// 获取对应 a b 最大值
	
	int A = maxs + 1;	// 根据对应的最大值，赋值一个元素范围外的元素作为 集合 A 的根节点
	int B = maxs + 2;	// 根据对应的最大值，赋值一个元素范围外的元素并且不同于集合A的根元素的元素作为 集合 B 的根节点
	father[A] = A,father[B] = B;	// 集合根节点初始化
	
	vector<int>v(n + 2,0);	// 存储对应元素
	for(int i = 1;i <= n;++i)
	{
		cin >> v[i];
		if(v[i] >= maxs)	// 如果存在 元素 大于 a 和 b ，那么放不了 任意集合，无解输出 NO
		{
			cout << "NO" << endl;
			return ;
		}
		pos[v[i]] = i;	// 映射对应的下标
		
		father[i] = i;	// 对应下标 根节点初始化
	}
	
	for(int i = 1;i <= n;++i)
	{
		// 如果对应的元素存在的话，我们将其元素的下标与当前的下标进行操作合并对应的集合
		
		if(pos[b - v[i]]) Union(i,pos[b - v[i]]);	// 另一元素存在 集合 b 那么我们合并对应下标 
		else Union(A,i);	//如果不符合那么合并另一个集合
		
		
		if(pos[a - v[i]]) Union(i,pos[a - v[i]]);	// 另一元素存在 集合 a 那么我们合并对应下标 
		else Union(B,i);	//如果不符合那么合并另一个集合
	}
	
	A = Finds(A),B = Finds(B);	// 根据对应的 结合 根节点元素查找；
	
	if(A == B) cout << "NO" << endl;	// 如果最终集合 A 和 集合 B 的根节点也给合并了，说明无解 NO
	else
	{
		cout << "YES" << endl;
		for(int i = 1;i <= n;++i)
		{
// 			cout << bool(Finds(i) == B) << ' ';		// 这样输出是错误的，有可能这里没考虑一个情况，就是 A == B 的时候，也有可能返回值的原因
			if(Finds(i) == A) cout << "0 ";
			else cout << "1 ";
		}
		cout << endl;
	}
}
 
signed main()
{
	IOS;
	int ___t = 1;
	while(___t--) solve();	
	return 0;
}