POJ1291-并查集/dfs

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


/*
思路：如果第x句说y是对的，则x，y必定是一起的，x+n，y+n是一起的；反之x，y+n//y，x+n是一起的。
	利用并查集判断 x 和 x+n 是否在同一集合。
	至于查找最多正确的话，对这些 “小树” 进行dfs即可。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> 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 x;
	return fa[x] = find( fa[x] );
}

void union_ab( int x,int y ){
	int fax = find( x );
	int fay = find( y );
	if( rank[ fax ]>rank[ fay ] ){
		fa[ fay ] = fax;
		rank[ fax ] += rank[ fay ];
	}
	else {
		fa[ fax ] = fay;
		rank[ fay ] += rank[ fax ];
	}
}

void dfs( int x,int n ){
	vis[ x ] = 1;
	if( x<=n ){
		vis[ x+n ] = 1;
		Cnt_true ++ ;
		//若x是正确的，则x+n则是错误的，同时也不用再去访问。
	}
	else {
		vis[ x-n ] = 1;
		Cnt_false ++ ;
	}
	for( int i=head[x];i!=-1;i=edge[i].next ){
		int y = edge[i].v;
		if( !vis[y] ){
			dfs( y,n );
		}
	}
}	

int main(){
	int n;
	while( scanf("%d",&n)==1,n ){
		init( n*2 );
		bool f = true;
		char s1[ 24 ],s2[ 24 ],s3[ 24 ];
		int x1,y1,x2,y2;
		int fax,fay;
		for( int i=1;i<=n;i++ ){
			scanf("%s%d%s%s",s1,&y1,s2,s3);
			x1 = i,x2 = i+n;
			y1 = y1,y2 = y1+n;
			//x1表示true，x2表示false
			if( f==false ) continue;
			if( s3[0]=='f' ){
				fax = find( x1 );
				fay = find( y1 );
				if( fax==fay ){
					f = false;
					continue;
				}
				fax = find( x2 );
				fay = find( y2 );
				if( fax==fay ){
					f = false;
					continue;
				}
				union_ab( x1,y2 );
				union_ab( x2,y1 );
				addedge( x1,y2 );
				addedge( x2,y1 );
			}
			else {
				
				fax = find( x1 );
				fay = find( y2 );
				if( fax==fay ){
					f = false;
					continue;
				}
				fax = find( x2 );
				fay = find( y1 );
				if( fax==fay ){
					f = false;
					continue;
				}
				
				union_ab( x1,y1 );
				union_ab( x2,y2 );
				addedge( x1,y1 );
				addedge( x2,y2 );
			}
		}
		if( f==false ) {
			puts("Inconsistent");
			continue;
		}//specail judge
		for( int i=1;i<=n;i++ ){
			if( find(i)==find(i+n) ){
				f = false;
				break;
			}
		}
		if( f==false ) {
			puts("Inconsistent");
			continue;
		}
		int ans = 0;
		for( int i=1;i<=2*n;i++ ){
			if( !vis[i] ){
				Cnt_false = Cnt_true = 0;
				dfs( i,n );
				ans += max( Cnt_true,Cnt_false );
			}
		}//find the max
		printf("%d\n",ans );
	}
	return 0;
}