#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 ， 谢谢。。 (1610) yangjinghe 2009-06-29 18:35:07
  • Re:哪位可以给点测试数据不？ 老WA ， 谢谢。。 (0) shi_mj 2009-07-25 21:05:48