首先很容易想到并查集维护,将相等的数merge起来。但是我们很难维护不等的情况。

那怎么办?

我们发现我们可以查询两数不等是否成立,只是不能维护它而已,并且事实上,不等没有类似\(a\ne b,b\ne c,\texttt{则}a\ne c\)的性质。

所以我们可以变更维护顺序。

先在并查集里维护等于的关系(也就是先处理\(e=1\)的约束),然后对于每一个不等约束条件\(a\ne b\),判断\(a,b\)是否在同一并查集里。

至于数据范围是\(10^9\),开个map把每一个出现的未知数编号对应到\([1,n]\)范围内的整数上就好了。

code:

#include
    
     using namespace std;int T,n,u,v,cnt,tu,tv,op,ne[100010][2],sz,f[200010];map
     
      mp;int getf(int x){    return f[x]==x?x:f[x]=getf(f[x]);}void merge(int x,int y){    if(getf(x)==getf(y))return;    f[f[x]]=f[y];}int main(){    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for(int i=1;i<=2*n;i++)f[i]=i;        mp.clear();        cnt=0;        sz=0;        for(int i=1;i<=n;i++){            scanf("%d%d%d",&u,&v,&op);            tu=mp[u];            if(!tu)tu=mp[u]=++cnt;            tv=mp[v];            if(!tv)tv=mp[v]=++cnt;            if(!op)ne[++sz][0]=tv,ne[sz][1]=tu;            else merge(tu,tv);        }        for(int i=1;i<=cnt;i++)getf(i);        for(int i=1;i<=sz;i++)            if(f[ne[i][0]]==f[ne[i][1]]){                puts("NO");                goto END;            }        puts("YES");        END:        ;    }    return 0;}