求助!#2 TLE
查看原帖
求助!#2 TLE
920947
yrteop_maerD楼主2024/5/2 10:33
#include<bits/stdc++.h> 
using namespace std;
#define int long long
int T,n,tep;

int b[1000005];
int tot;
map<int,int> fa;

inline int find(int x){
	if (fa[x]!=x){
		fa[x]=find(fa[x]);
	}
	return fa[x];
}

struct node{
	int x,y,op;
}a[1000005];

inline bool cmp(node s,node t){
	if (s.op!=t.op) return s.op>t.op;
	return s.x<t.x;
}



signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--){
		tot=0;
		cin>>n;
		for (int i=1;i<=n;i++){
			cin>>a[i].x>>a[i].y>>a[i].op;
			b[++tot]=a[i].x;
			b[++tot]=a[i].y;
		}
		sort(b+1,b+tot+1);
		tot=unique(b+1,b+tot+1)-b-1;
		for (int i=1;i<=tot;i++){
			fa[b[i]]=b[i];
		}
		tep=1;
		sort(a+1,a+n+1,cmp);
		for (int i=1;i<=n;i++){
			int u=find(a[i].x),v=find(a[i].y);
			if (a[i].op){
				fa[u]=v;	
			}
			else{
				if (u==v){
					cout<<"NO\n";
					tep=0;
					break;
				}
			}
		}
		if (tep) cout<<"YES\n";
	}
	
	return 0;
}
2024/5/2 10:33
加载中...