Dowemo

.

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>


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;


}









Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs