求助(玄关)
查看原帖
求助(玄关)
1050483
zjr2014楼主2024/11/7 19:56
#include<bits/stdc++.h>
using namespace std;
int read(){
	int r=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')r=(r<<3)+(r<<1)+(c^48),c=getchar();
	return r*f;
}
void file(string s){
	s+=".in";
	freopen(s.c_str(),"r",stdin);
	s.pop_back();
	s.pop_back();
	s.pop_back();
	s+=".out";
	freopen(s.c_str(),"w",stdout);
}
void IOS(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
int fa[499000001],n,t,e,x,y,ans;
struct q{
	int x,y,e;
	bool operator<(q b){
		return e>b.e;
	}
};
vector<int>d;
vector<q>qq;
int find(int x){
	return fa[x]==0?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
int main(){
	t=read();
	while(t-->0){
		ans=1;
		n=read();
		d.clear();
		qq.clear();
		for(int i=1;i<=n;i++){
			x=read();
			y=read();
			e=read();
			qq.push_back({x,y,e});
		}
		sort(qq.begin(),qq.end());
		for(q i:qq){
			if(i.e==1){
				merge(i.x,i.y);
			}
			else{
				if(find(i.x)==find(i.y)){
					ans=0;
				}
			}
			d.push_back(i.x);
			d.push_back(i.y);
		}
		if(ans==1){
			putchar('Y');
			putchar('E');
			putchar('S');
		}
		else{
			putchar('N');
			putchar('O');
		}
		for(int i:d){
			fa[i]=0;
		}
		putchar('\n');
	}
	return 0;
}
2024/11/7 19:56
加载中...