#include<stdio.h>
int father[100010];
int find(int x)
{
	if(father[x]==x)
		return x;
	else
	{
		int temp=find(father[x]);
		father[x]=temp;
		return father[x];
		
	}
}

void Union(int x,int y)
{
	father[x]=y;
}

int main()
{
	int t,m,n,p,l;
	int i,j;
	while(scanf("%d",&t)==1)
	{
		p=1;l=1;
		while(t--)
		{
			scanf("%d%d",&n,&m);
			for(i=1;i<=n;i++)
				father[i]=i; 
			father[n+1]=n+1;
			father[n+2]=n+2;
			char q;
			getchar();
			while(m--)
			{
				
				scanf("%c%d%d",&q,&i,&j);
				getchar();
				if(q=='A')
				{
					if(p==1)
					{
						printf("Not sure yet.\n");
						p=0;
					}
					else
					{
						if(find(i)==find(j))
							printf("In the same gang.\n");
						else
							printf("In different gangs.\n");
					}
				}
				else
				{
					if(q=='D')
					{
						if(l==1)
						{
							Union(i,n+1);
							Union(j,n+2);
							l=0;
						}
						else
						{
							int t1=find(i),t2=find(j);
							if(t1==n+1||t1==n+2)
								Union(t2,2*n+3-t1);
							else
								if(t2==n+1||t2==n+2)
									Union(t2,2*n+3-t2);
						}
					}
				}
			}
			
		}
		
	}
	return 0;
}

• 补充下我的想法 (79) H3100402060 2011-02-20 21:36:48