题目
我居然会做noi的题目233。
还是比较简单的了，先把所有相等的用并查集放在一个集合中，最后再判断不相等的是否在同一集合中。
由于数很大，我们应该先离散化，不过n<=1000000排序有点卡吧，所以我们尝试用map来记录父亲。
#include<bits/stdc++.h> using namespace std; #define N 1000000 map <int,int> f; int p[N+1][2],x,y,num; int n,T,opt; int find(int x) { return x==f[x]?x:f[x]=find(f[x]); } void error() { putchar('N'); putchar('O'); putchar('\n'); } void success() { putchar('Y'); putchar('E'); putchar('S'); putchar('\n'); } int main() { //freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { scanf("%d",&n); f.clear();num=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&opt); if(!f.count(x))f[x]=x; if(!f.count(y))f[y]=y; if(opt) { int fx=find(x),fy=find(y); f[fx]=fy; } else p[++num][0]=x,p[num][1]=y; } bool flag=true; for(int i=1;i<=num;i++) { int fx=find(p[i][0]),fy=find(p[i][1]); if(fx==fy) { flag=false; break; } } if(flag)success(); else error(); } return 0; }