本文共 1516 字，大约阅读时间需要 5 分钟。
等于有传递性，所以hash一下把等于用并查集连起来，然后再判断不等于是否合法即可
#include #include #include #include using namespace std;const int N=200005;int T,n,x,y,v,f[N],g[N],tot,has;bool fl; map mp;struct qwe{ int a,b,o; }a[N];int read(){ int r=0,f=1; char p=getchar(); while(p>'9'||p<'0') { if(p=='-') f=-1; p=getchar(); } while(p>='0'&&p<='9') { r=r*10+p-48; p=getchar(); } return r*f;}int zhao(int x){ return x==f[x]?x:f[x]=zhao(f[x]);}int main() { T=read(); while(T--) { n=read(); fl=0,tot=0,has=0; for(int i=1;i<=n;i++) { a[i].a=read(),a[i].b=read(),a[i].o=read(); g[++tot]=a[i].a,g[++tot]=a[i].b; } sort(g+1,g+1+tot); for(int i=1;i<=tot;i++) if(i==1||g[i]!=g[i-1]) mp[g[i]]=++has; for(int i=1;i<=n;i++) a[i].a=mp[a[i].a],a[i].b=mp[a[i].b]; for(int i=1;i<=has;i++) f[i]=i; for(int i=1;i<=n;i++) if(a[i].o) { int fu=zhao(a[i].a),fv=zhao(a[i].b); if(fu!=fv) f[fu]=fv; } for(int i=1;i<=n&&!fl;i++) if(!a[i].o&&zhao(a[i].a)==zhao(a[i].b)) fl=1; if(fl) puts("NO"); else puts("YES"); } return 0; }
转载于:https://www.cnblogs.com/lokiii/p/9649809.html