记录编号	587172	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]程序自动分析	最终得分	100
用户昵称	增强型图元文件	是否通过	通过
代码语言	C++	运行时间	2.654 s
提交时间	2024-03-17 18:08:26	内存使用	7.15 MiB

#include <bits/stdc++.h>
using namespace std;
const int MAXN=400010;

struct op{
	int a,b,e;
};
bool cmp(op x,op y){
	return x.e>y.e;
}
int fa[MAXN],n,T,cnt;
map<int,int> mp;
op ops[MAXN];
void init(){
	for(int i=0;i<MAXN;i++){
		fa[i]=i;
	}
	cnt=1;
	map<int,int> tmp;
	mp=tmp;
}
int get(int x){
	if(fa[x]==x)return x;
	return fa[x]=get(fa[x]);
}
void merge(int x,int y){
	int ta=get(x);
	int tb=get(y);
	if(ta==tb)return;
	fa[ta]=tb;
}
int getct(int tg){
	if(!mp[tg]){
		mp[tg]=cnt;
		cnt++;
	}
	return mp[tg];
}

int main(int argc, char** argv) {
	freopen("prog.in","r",stdin);
	freopen("prog.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n;
		init();
		bool flag=true;
		
		for(int i=1;i<=n;i++){
			int a,b,e;
			cin>>a>>b>>e;
			op tm;tm.a=a;tm.b=b;tm.e=e;
			ops[i]=tm;
		}
		sort(ops+1,ops+1+n,cmp);
		for(int i=1;i<=n;i++){
			if(ops[i].e==1){
				merge(getct(ops[i].a),getct(ops[i].b));
			}else{
				int ta=get(getct(ops[i].a));
				int tb=get(getct(ops[i].b));
				if(ta==tb){
					flag=false;
					break;
				}
			}
		}
		if(flag){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}