70分求调!!!
查看原帖
70分求调!!!
1191361
daixihan楼主2025/7/24 19:28
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{
	int x,y,z;
}a[N];
int T,n,fa[N],cnt,b[N];
bool cmp(node q,node w){
	return q.z>w.z;
}
int find(int x){
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
bool check(){
	for(int i=1;i<=n;i++){
		if(a[i].z) fa[find(a[i].x)]=find(a[i].y);
		else{
			if(find(a[i].x)==find(a[i].y)){
				return 0;
			}
		}
	}
	return 1;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		cnt=0;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(fa,0,sizeof(fa));
		for(int i=1;i<=n;i++){
			cin>>a[i].x>>a[i].y>>a[i].z;
			b[++cnt]=a[i].x;
			b[++cnt]=a[i].y;
			fa[i]=i;
		}
		sort(b+1,b+1+cnt);
		int res=unique(b+1,b+1+cnt)-(b+1); 
		for(int i=1;i<=n;i++){
			a[i].x=lower_bound(b+1,b+res+1,a[i].x)-b;
			a[i].y=lower_bound(b+1,b+res+1,a[i].y)-b;
		}
		sort(a+1,a+n+1,cmp);
		if(check()){
			cout<<"YES\n";
		}
		else cout<<"NO\n";
	}
	return 0;
}
2025/7/24 19:28
加载中...