50pts求助,map+并查集
查看原帖
50pts求助,map+并查集
1017629
ZSB00000楼主2024/3/16 20:41
#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int, int>father;
struct node
{
	int e,x,y;
};
vector<node>aaa;
int find(int x) {
	return x == father[x] ? x : father[x] = find(father[x]);
}
void unionn(int x, int y) {
	father[find(x)] = find(y);
}
void work(void)
{
	aaa.clear();
	father.clear();
	int tot=0;
	int n;
	cin>>n;
	for(int i=1;i<=2*n;i++)
	{
		father[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int e,x,y;
		cin>>x>>y>>e;	
		if(e==1)
		{
			unionn(x,y);
		}
		else if(e==0)
		{
			tot++;
			aaa.push_back(node{e,x,y});
		}
	}
	for(int i=0;i<tot;i++)
	{
		if(aaa[i].e==0&&find(aaa[i].x)==find(aaa[i].y)/*&&find(aaa[i].x)!=0*/)
		{
		//	cout<<aaa[i].x<<" "<<aaa[i].y<<" "<<find(aaa[i].x)<<" "<<find(aaa[i].y)<<endl;
			cout<<"NO"<<endl;
			return;
		}
	}
	cout<<"YES"<<endl;
}
signed main()
{
//	freopen("P1955_2.in","r",stdin);
	int t;
	cin>>t;
	while(t--)
	{
		work();
	}
}
/*
9
24 234 1		24=234
2837 1 1		2837=1=23
235 877 1		235=877=987
242 78 0		
23 1 1
223 977 0
254 76 1		254=76
235 987 0
877 987 1		*/
2024/3/16 20:41
加载中...