[cpp] view plaincopyprint 
并查集  
题意：找出给定的这些话中是否有冲突。若没有则最多有多少句是对的。  
并查集
题意：找出给定的这些话中是否有冲突。若没有则最多有多少句是对的。



[cpp] view plaincopyprint 
/* 
思路：如果第x句说y是对的，则x，y必定是一起的，x+n，y+n是一起的；反之x，y+n//y，x+n是一起的。 
    利用并查集判断 x 和 x+n 是否在同一集合。 
    至于查找最多正确的话，对这些 “小树” 进行dfs即可。 
*/  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
using namespace std;  
typedef long long int64;  
//typedef __int64 int64;  
typedef pair PII;  
#define MP(a,b) make_pair((a),(b))   
const int maxn = 2005;  
const int inf = 0x7fffffff;  
const double pi=acos(-1.0);  
const double eps = 1e-8;  
  
int fa[ maxn ];  
int rank[ maxn ];  
struct Edge{  
    int u,v,next;  
}edge[ maxn<<1 ];  
int cnt,head[ maxn ];  
int vis[ maxn ];  
int Cnt_true,Cnt_false;  
  
void init( int n ){  
    cnt = 0;  
    //Cnt_true = Cnt_false = 0;  
    memset( head,-1,sizeof( head ) ) ;  
    for( int i=1;i<=n;i++ ){  
        fa[ i ] = i;  
        rank[ i ] = 1;  
        vis[ i ] = 0;  
    }  
}  
  
void addedge( int a,int b ){  
    edge[ cnt ].u = a;  
    edge[ cnt ].v = b;  
    edge[ cnt ].next = head[ a ];  
    head[ a ] = cnt ++ ;  
      
    edge[ cnt ].u = b;  
    edge[ cnt ].v = a;  
    edge[ cnt ].next = head[ b ];  
    head[ b ] = cnt ++ ;  
}  
  
int find( int x ){  
    if( x==fa[x] )  
        return