20分RE!求调
查看原帖
20分RE!求调
1283976
sllhy7楼主2025/2/6 09:24
#include<bits/stdc++.h>
using namespace std;
long long n,t,fa[200010],jl,le;
bool fl;
map<long long,long long> zh;
struct st{
	long long i,j,e;
}a[200010];
long long fin(long long x){
	if(fa[x]==x) return x;
	if(fa[x]!=x){
		fa[x]=fin(fa[x]);
	}
	return fa[x];
}
void build(long long x,long long y){
	long long xx=fin(x),yy=fin(y);
	if(xx!=yy){
		fa[xx]=yy;
	}
	return ;
}
bool cmp(st xxx,st yyy){
	if(xxx.e==0&&yyy.e==1) return 0;
	return 1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	for(long long iii=1;iii<=t;iii++){
		memset(fa,0,sizeof(fa));
		memset(a,0,sizeof(a));
		fl=1;
		cin>>n;
		le=0;
		jl=1;
		for(long long jjj=1;jjj<=n;jjj++){
			cin>>a[jjj].i>>a[jjj].j>>a[jjj].e; 
			if(zh[a[jjj].i]==0){
				zh[a[jjj].i]=jl;
				fa[zh[a[jjj].i]]=zh[a[jjj].i];
				le++;
				jl++;
			}
			if(zh[a[jjj].j]==0){
				zh[a[jjj].j]=jl;
				fa[zh[a[jjj].j]]=zh[a[jjj].j];
				le++;
				jl++;
			}
			a[jjj].i=zh[a[jjj].i];
			a[jjj].j=zh[a[jjj].j];
		}
		
		sort(a+1,a+n+1,cmp);		
		for(long long jjj=1;jjj<=n;jjj++){
			if(a[jjj].e==1){
				build(a[jjj].i,a[jjj].j);
			}
			else{
				long long aaa=fin(a[jjj].i);
				long long bbb=fin(a[jjj].j);
				if(aaa==bbb){
					fl=0;
					break;
				}
			}
		}
		if(fl==1) cout<<"YES\n";
		else cout<<"NO\n";
		zh.clear();
	}
	return 0;
}
2025/2/6 09:24
加载中...