30pts求助
查看原帖
30pts求助
753887
ZLRest楼主2023/8/18 10:01
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,n;
int f[100010000];
map<int,int> m;
vector <int> v;
struct node{
	int a,b,c;
}q[1001000];
int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void add(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy) f[fy]=fx;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		bool b=0;
		scanf("%lld",&n);
		v.clear();
		for(int i=1;i<=5*n;i++) f[i]=i;
		for(int i=1;i<=n;i++) {
			scanf("%lld%lld%lld",&q[i].a,&q[i].b,&q[i].c);
			v.push_back(q[i].a);
			v.push_back(q[i].b);
		}
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		for(int i=0;i<v.size();i++) m[v[i]]=i+1;
		for(int i=1;i<=n;i++){
			if(q[i].c==1) {
				add(m[q[i].a],m[q[i].b]);
			}
			else{
				int fx=find(m[q[i].a]),fy=find(m[q[i].b]);
				if(fx==fy) {
					b=1;
					printf("NO\n");
					break;
				}
			}
		}
		if(b==0)
		printf("YES\n");
		
		
	}
}
2023/8/18 10:01
加载中...