题号1575 C.难度排名 (并查集知识点)

原创于 2023-11-02 17:46:46 发布 · 粉丝可见 · 274 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/134187728

题目：

样例1：

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

No

样例2：

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

Yes

思路：

这题，有两种情况是由矛盾的。

第一种情况：当前题号存在大于两个题号的相连，情况是矛盾的，输出No

第二种情况：出现了环的形式相连，情况是矛盾的，输出 No

其余都可以蒙混过关。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#define endl '\n'
#define Yes puts("Yes")
#define No puts("No")
#define umap unordered_map
#define uset unordered_set
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
 
int n,m;
 
umap<int,int>p;	// 存储题号的根结点
 
// 查找对应题号的根节点
inline int Find(int x)
{
	int t = x;
	while(x != p[x])x = p[x];
	p[t] = x;
	return x;
}
// 初始化存储题号的根结点
inline void Init()
{
	for(int i = 1;i <= n;++i) p[i] = i;
}
inline void solve()
{
	// 存储对应题号所连接的题号
	// 由于可能会重复，所以利用set去重
	umap<int,uset<int>>v;
	
	cin >> n >> m;
	
	Init();	// 初始化根题号
	
	bool st = false;	// 标记是否出现环形相连情况
	while(m--)
	{
		int a,b;
		cin >> a >> b;
		v[a].emplace(b);
		v[b].emplace(a);
		
		// 查找对应题号的根题号
		a = Find(a),b = Find(b);
		// 如果还没相连，那么我们相连
		// 如果我们之前相连过，现在再说的一次
		// 说明出现了 环形相连，矛盾了，输出 No
		if(a != b) p[a] = b;
		else
		{
			st = true;
		}
	}
	if(st)
	{
		No;
		return ;
	}
	// 循环查找是否有哪个题号大于了应该相连的两个数量的题号
	for(int i = 1;i <= n;++i)
	{
		// 如果出现了，说明矛盾了，输出答案
		if(v[i].size() > 2)
		{
			No;
			return ;
		}
	}
	
	// 否则可以蒙混过关
	Yes;
}
 
int main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}