关于我样例过了但RE???
查看原帖
关于我样例过了但RE???
1185854
ly_magician楼主2024/12/3 21:40
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long T,t[N],fa[N];
struct nnd{
	int x,y,e;
}a[N];
int find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
} 
int me(int x,int y){
	int fx=find(x),fy=find(y);
	fa[fy]=fx;
}
bool cmp(nnd x,nnd y){return x.e>y.e;}
int main(){
	scanf("%d",&T);
	while(T--){
		memset(t,0,sizeof(t));
		long long n,tp=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].e);
			t[++tp]=a[i].x,t[++tp]=a[i].y;
		}
		sort(t+1,t+tp+1);
		int l=unique(t+1,t+tp+1)-t-1;
		for(int i=1;i<=n;i++){
			a[i].x=lower_bound(t+1,t+l+1,a[i].x)-t-1;
			a[i].y=lower_bound(t+1,t+l+1,a[i].y)-t-1;
		}
		for(int i=1;i<=l;i++) fa[i]=i;
		sort(a+1,a+n+1,cmp);
		bool fg=true;
		for(int i=1;i<=n;i++){
			if(a[i].e==1) me(t[a[i].x],t[a[i].y]);
			else {
				if(find(t[a[i].x])==find(t[a[i].y]))
					fg=false;
			}
		}
		if(fg) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}//求调
2024/12/3 21:40
加载中...