蒟蒻求助有注释悬棺
查看原帖
蒟蒻求助有注释悬棺
1053122
shy_lihui楼主2024/12/17 00:11
#include<bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int,int> um;
int t,n;
int fa[10000005];
int findfa(int u)//找爸爸 
{
	if(fa[u]==u)
	{
		return u;
	}
	return fa[u]=findfa(fa[u]);
}
set<int> s;//要离散化的数 
struct node//每两个变量之间的关系 
{
	int x,y,e;
};
bool cmp(node x,node y)//把等式放到前面 
{
	return x.e==1;
}
vector<node> v;//存关系 
void slove()
{
	cin>>n;
	for(int i=1;i<=n;i++)//输入所有关系 
	{
		node q;
		cin>>q.x>>q.y>>q.e;
		v.push_back(q);//放进关系 
		s.insert(q.x);//放进set离散化 
		s.insert(q.y);//离散化 
	}
	int x=1;//离散化从1开始 
	for(auto i:s)
	{
		um[i]=x;//把 i 缩成 x 
		x++;
		fa[x]=x;//顺便就可以预处理father数组 
	}
	sort(v.begin(),v.end(),cmp);//等式靠前 
	for(auto i:v)
	{
		int u=um[i.x];//直接取离散化之后的结果 
		int v=um[i.y];//直接取离散化之后的结果 
		int f=i.e;
		if(f==1)//如果关系为等式 
		{
			int fau=findfa(u);//找爸爸 
			int fav=findfa(v);//找爸爸 
			fa[fau]=fav;//合并爸爸 
		}
		else//如果是不等式 
		{
			int fau=findfa(u);//找到爸爸并判断是否一样 
			int fav=findfa(v);
			if(fau==fav)//如果一样则不满足不等式 
			{
				cout<<"NO\n";
				return;
			}
		}
	}
	cout<<"YES\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while(t--)
	{
		slove();
	}
	return 0;
}

2024/12/17 00:11
加载中...