有10^9个点,每次给出两个点的关系:权相等或不等,问最后能不能成立
感觉一开始在撕烤一个动态的问题,,,想写一个带权的并查集
结果发现静态询问,那就sb乱搞,懒得手写离散就直接map(卧槽好多细节忘考虑)
#include <bits/stdc++.h>
using namespace std;
int T,n,N,Nm,x,y,e;
map<int,int> o;
int fa[],X[],Y[];
int getfa(int x)
{
if(fa[x]==x) return x;
else return fa[x]=getfa(fa[x]);
}
int main()
{
for(scanf("%d",&T);T;T--)
{
scanf("%d",&n);Nm=;N=;o.clear();
for(int i=;i<=*n;i++)
fa[i]=i;
bool over=;
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&e);
if(over) continue;
if(x==y)
{
if(e==)
{
over=;
puts("NO");
}
else
continue;
}
int Xx=o[x],Yx=o[y];
if(!Xx)o[x]=++Nm,x=Nm;else x=Xx;
if(!Yx)o[y]=++Nm,y=Nm;else y=Yx;
if(e)
fa[getfa(x)]=getfa(y);
else
X[++N]=x,Y[N]=y;
}
if(over) continue;
bool flag=;
for(int i=;i<=N;i++)
if(getfa(X[i])==getfa(Y[i]))
flag=;
puts(flag?"NO":"YES");
}
return ;
}