水并查集
#include<cstdio>
#include<algorithm>
using namespace std;
int t,n,f[1000005],g[1000005],index=0,ind;
struct Node{
int a,b,o;
}node[1000005];
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int x,int y){if(x>y)f[x]=y;else f[y]=x;}
int main(){
freopen("4195.in","r",stdin);
freopen("4195.out","w",stdout);
scanf("%d",&t);
while(t--){
scanf("%d",&n);
ind=0;
for(int i=1;i<=n;i++){
scanf("%d %d %d",&node[i].a,&node[i].b,&node[i].o);
g[++ind]=node[i].a;
g[++ind]=node[i].b;
}
sort(g+1,g+ind+1);
ind=unique(g+1,g+ind+1)-g-1;
for(int i=1;i<=n;i++){
node[i].a=lower_bound(g+1,g+ind+1,node[i].a)-g;
node[i].b=lower_bound(g+1,g+ind+1,node[i].b)-g;
}
for(int i=1;i<=ind;i++)f[i]=i;
for(int i=1;i<=n;i++){
if(node[i].o==1){Union(Find(node[i].a),Find(node[i].b));}
}
int flag=0;
for(int i=1;i<=n;i++){
if(node[i].o==0 && Find(node[i].a)==Find(node[i].b)){puts("NO");flag=1;break;}
}
if(!flag)puts("YES");
}
return 0;
}
评论 (0)
