并查集,忘了.自己写也可以写出来,wow..
#include <bits/stdc++.h> using namespace std; const int N=1e6+5; unordered_map<int,int>fa; struct vv{ int l,r,p; }a[N]; int f(int x) { if(fa[x]!=x) return fa[x]=f(fa[x]); else return fa[x]=x; } int main() { int T; scanf("%d",&T); while(T--) { int n; fa.clear(); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].p); fa[a[i].l]=a[i].l;fa[a[i].r]=a[i].r; } for(int i=1;i<=n;i++)//把所有相同的归并. { if(a[i].p==1) { if(fa[a[i].l]!=a[i].l&&fa[a[i].r]!=a[i].r) { int ta=f(a[i].l);int tb=f(a[i].r); if(ta!=tb) { fa[tb]=ta; } } else if(fa[a[i].l]!=a[i].l) { int ta=f(a[i].l); fa[a[i].r]=ta; } else if(fa[a[i].r]!=a[i].r) { int tb=f(a[i].r); fa[a[i].l]=tb; } else { fa[a[i].l]=a[i].r; } } } int flag=0; for(int i=1;i<=n;i++)//把所有不相同的判断. { if(a[i].p==0) { if(f(a[i].l)==f(a[i].r)) { flag=1; break; } } } if(flag) puts("NO"); else puts("YES"); } return 0; }