90分求助大佬,第三个点wa了
查看原帖
90分求助大佬,第三个点wa了
148092
Dark_lightrq楼主2022/8/18 09:46
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,c;
}a[1000005];
int fa[4000005];
int b[2000005];
int n; 
int find(int x){
	return fa[x]^x?fa[x]=find(fa[x]):x;
}
bool cmp(node a,node b){
	return a.c>b.c;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int tot=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
			b[++tot]=a[i].x;
			b[++tot]=a[i].y;
		}
		sort(b+1,b+1+tot);
		int cnt=unique(b+1,b+1+tot)-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;
		}
		for(int i=1;i<=cnt;i++)fa[i]=i;
		sort(a+1,a+1+n,cmp);
		bool flag=0;
		for(int i=1;i<=n;i++){
			if(a[i].c){
				fa[find(a[i].x)]=find(a[i].y); 
			}
			else {
				if(find(a[i].x)==find(a[i].y)){
					flag=1;
					printf("NO\n");
					break;
				}
			}
		}
		if(!flag)printf("YES\n");
	}


	return 0;
}

2022/8/18 09:46
加载中...