POJ1291-并查集/dfs - c++编程基础

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;

}

/* 思路：如果第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 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; }

POJ1291-并查集/dfs(五)