一看到种类就想到关押罪犯那题,于是用种类并查集,不知道为啥只有70。。。
#include<bits/stdc++.h>
using namespace std;
#define N 1000003
int fa[N*2],book[N*2];
struct data{
int x,y,e;
}h[N];
void init(int s){
for(int i=0;i<=(s<<1);i++)fa[i]=i;
}
int find(int x){
if(fa[x]==x)return fa[x];
fa[x]=find(fa[x]);
return fa[x];
}
void merge(int x,int y){
x=find(x);y=find(y);
fa[x]=y;
}
bool check(int x,int y){
return find(x)==find(y);
}
// bool cmp(data a,data b){
// return a.e>b.e;
// }
int main(){
int t,n,book[N*3];
scanf("%d",&t);
for(int i=1;i<=t;i++){
scanf("%d",&n);
int tot=-1;
memset(book,0,sizeof(book));
memset(h,0,sizeof(h));
for(int j=1;j<=n;j++){
scanf("%d %d %d",&h[j].x,&h[j].y,&h[j].e);
book[++tot]=h[j].x;
book[++tot]=h[j].y;
}
sort(book,book+tot);
int reu=unique(book,book+tot)-book;
for(int j=1;j<=n;j++){
h[j].x=lower_bound(book,book+reu,h[j].x)-book;
h[j].y=lower_bound(book,book+reu,h[j].y)-book;
}
init(n);
// sort(h+1,h+n+1,cmp);
int flag=1;
for(int j=1;j<=n;j++){
if(h[j].e){
if(check(h[j].x+n,h[j].y)||check(h[j].x,h[j].y+n)){
flag=0;printf("NO\n");break;
}
else{
merge(h[j].x,h[j].y);
merge(h[j].x+n,h[j].y+n);
}
}else{
if(check(h[j].x,h[j].y)||check(h[j].x+n,h[j].y+n)){
flag=0;printf("NO\n");break;
}
else{
merge(h[j].x+n,h[j].y);
merge(h[j].x,h[j].y+n);
}
}
}
if(flag){
printf("YES\n");
}
}
return 0;
}