Dowemo
0 0 0 0

.

I'll do noi is title 233.

It's simple, first to put all equal use and set up a set in a collection, and finally determine whether the equality is in the same set.

Because the number is large, we should be discretization, but n <= 1000000 sorts a bit of card, so we try to use map to record the father.

#include<bits/stdc++.h>usingnamespacestd;#define N 1000000map <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();
 }
 return0;
}



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs