题解:并查集,因为数据比较大嘛,你要是想再所以如果开1e9的数组大小,那毫无疑问,基佬紫等着你。
所以这个题离散化用了map这个容器。
首先,遍历一遍e=1的时候,把他们之间相等的都给连到同一个集合里去,其次再遍历一遍e=0的时候,看一下当e=0的时候,这两个是是不是已经在同一个集合里面了,如果在一个集合里面的话,就说明这两个条件是冲突的,直接输出NO即可。
如何使用map:我们设一个cnt变量从0开始,没遇到一个没有遇到的数,就把他的值变换成++cnt即可,这样就可以把1e9的范围大小给缩小成2e5的范围。
这个题要注意的几点:
1.可能会存在2 2 0这种条件,所以要特判一下。
2.注意f[x]要开双倍的空间!!!!!
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;map<ll,int> s;
int a[maxn],b[maxn],c[maxn];
int f[maxn<<1];
void init(int x){for(int i=0;i<=2*x;i++) f[i]=i;s.clear();
}
int ifind(int x){if(f[x]==x) return x;else return f[x]=ifind(f[x]);
}
int main(){int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);init(n);int cnt=0;for(int i=0;i<n;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);if(c[i]){int nx=s[a[i]],ny=s[b[i]];if(!nx) s[a[i]]=++cnt,nx=cnt;if(!ny) s[b[i]]=++cnt,ny=cnt;int dx=ifind(nx);int dy=ifind(ny);if(dx!=dy) f[dx]=f[dy];//cout<<dx<<" "<<dy<<endl;}}bool flag=false;//for(int i=1;i<=4;i++) cout<<f[i]<<" ";for(int i=0;i<n;i++){if(!c[i]){int nx=s[a[i]];int ny=s[b[i]];if(a[i]==b[i]){flag=true;break;}if(!nx||!ny) continue;int dx=ifind(nx);int dy=ifind(ny);//cout<<dx<<" "<<dy<<endl;if(dx==dy){flag=true;break;}}}if(flag) cout<<"NO"<<endl;else cout<<"YES"<<endl;}return 0;
}