> #include <iostream>
> using namespace std;
> 
> #define N 100018
> 
> int p[N], r[N], rank[N]; 
> 
> int find( int x )
> {
> 	if( x==p[x] )
> 		return p[x];
> 	else
> 		return find( p[x] );
> }
> void merge( int root1, int root2 )
> {
> 	int x, y;
> 	x=find( root1 );
> 	y=find( root2 );
> 	if( rank[x]>rank[y] )
> 		p[y] = x;
> 	else
> 	{
> 		p[x] = y;
> 		if( rank[x]==rank[y] )
> 			rank[y]++;
> 	}	
> }
> int main() 
> {
> 	//freopen( "in.txt", "r", stdin );
> 
> 	int n, k, scena;
> 	char c;
> 	int i, j;
> 	int x, y;
> 	int a, b;
> 
> 	scanf( "%d", &scena );
> 	
> 	while(scena--)
> 	{
> 		scanf( "%d %d", &n, &k );
> 		getchar();
> 		for( i=1; i<=n; i++ )
> 		{
> 			p[i] = i;
> 			r[i] = i;
> 		}
> 		memset( rank, 0, sizeof(rank) );
> 
> 		for( i=0; i<k; i++ )
> 		{
> 			scanf( "%c %d %d",&c, &x, &y );
> 			getchar();
> 			
> 			a=find(x);
> 			b=find(y);
> 
> 			if( c=='D' )
> 			{	
> 				if( r[x] != x )
> 					merge( r[x], b );
> 				else
> 					r[x] = b;
> 
> 				if( r[y] != y )
> 					merge( r[y], a );
> 				else
> 					r[y] = a;
> 			}
> 
> 			else if( c=='A' )
> 			{
> 				if(  a==b  )
> 				{
>                                         printf( "In the same gang.\n" );
> 					
> 				}
> 				else if( a!=b &&( a!=r[a]||b!=r[b] ) )
> 				{
>                                         printf( "In different gangs.\n" );
> 					
> 				}
> 				else
> 				{
>                                         printf( "Not sure yet.\n" );
> 				}
> 		       }
> 
> 	     }
>         }
> 	return 0;
> }
> 
> 

• Re:哪位可以给点测试数据不？ 老WA ， 谢谢。。 (0) shi_mj 2009-07-25 21:05:48