WA 30pts
查看原帖
WA 30pts
794701
wo_hen_la楼主2024/3/3 09:48
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int t,n;
int b[N],f[N];
struct node
{
	int x,y;
	bool op;
}a[N];
int find(int x)
{
	return f[x]==x?x:f[x]=find(f[x]);
}
bool cmp(node x,node y)
{
	return x.op>y.op;
}
int main()
{
	cin>>t;
	while(t--){
		int cnt=0;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i].x>>a[i].y>>a[i].op;
			b[++cnt]=a[i].x,b[++cnt]=a[i].y;
			f[i]=i;
		}
		sort(b+1,b+1+cnt);
		int len=unique(b+1,b+1+cnt)-b;
		for(int i=1;i<=n;i++){
			a[i].x=lower_bound(b+1,b+1+cnt,a[i].x)-b;
			a[i].y=lower_bound(b+1,b+1+cnt,a[i].y)-b;
		}
		sort(a+1,a+1+n,cmp);
		bool flag=0;
		for(int i=1;i<=n;i++){
			int x=find(a[i].x),y=find(a[i].y);
			if(a[i].op) f[y]=x;
			else{
				if(x==y){
					flag=1;
					break;
				}
			}
		}
		if(!flag) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}
2024/3/3 09:48
加载中...