90分求助
查看原帖
90分求助
692377
Faker__Insane楼主2024/3/30 18:48
#include<bits/stdc++.h> 
using namespace std;
struct evan{
	int x,y,z;
};
const int maxn=100005;
bool cmp(evan x,evan y)
{
	return x.z>y.z;
}
int s[maxn];
int find(int n)
{
	if(s[n]==n) return n;
	return s[n]=find(s[n]);
}
evan a[maxn];
int b[maxn<<2];
int n;
int main()
{
	int Q;
	cin>>Q;
	while(Q--)
	{
		cin>>n;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(s,0,sizeof(s));
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].x>>a[i].y>>a[i].z;
			b[sum+1]=a[i].x;
			sum++;
			b[sum+1]=a[i].y;
			sum++;
		}
		sort(b+1,b+sum+1);
		int sum2=unique(b+1,b+sum+1)-b;
		for(int i=1;i<=n;i++)
		{
			a[i].x=lower_bound(b+1,b+sum2+1,a[i].x)-b;
			a[i].y=lower_bound(b+1,b+sum2+1,a[i].y)-b;
		}
		for(int i= 1;i<=sum2;i++)
		{
			s[i]=i;
		}
		sort(a+1,a+n+1,cmp);
		bool flag=true;
		for(int i=1;i<=n;i++)
		{
			if(a[i].z==1)
			{
				if(find(a[i].x)!=find(a[i].y))
				{
					s[find(a[i].x)]=find(a[i].y);

				}
			}
			else if(find(a[i].x)==find(a[i].y))
			{
				flag=false;
				break;
			}
		}
		if(flag==true) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;

}

90分求助

2024/3/30 18:48
加载中...