#include "cstdio"
#include "memory.h"

const int MAXN = 100010;

//set记录其代表元素，rank代表集合中的层数；
int set[MAXN],rank[MAXN];
int w[MAXN] = {0}; //每个人与其父亲的权值
int adjust;
//返回一个包含X的子集。
int FindSet(int x,int& sum)
{
    if(set[x]!=x)
	{
		sum += w[x];
		set[x] = FindSet(set[x],sum);
	}
	return set[x];
}

//生成一个单元素集合{X}。这个操作对集合S的每一个元素只能应用一次。
void MakeSet(int x)
{
    set[x]=x;
    rank[x]=0;
}

//
void Link(int a,int b)
{
    if(rank[a]>rank[b])
	{
		set[b]=a;
		w[b] = adjust;
	}
    else if(rank[a]<rank[b])
	{
		set[a]=b;
		w[a] = adjust;
	}
    else
    {
        set[a]=b;
        rank[b]++;
		w[a] = adjust;
    }
}

//构造分别包含X和Y的不相交子集的并集，并把它添加到子集的集合中，以代替被删除的两个子集；
void Union(int a,int b)
{
	int p = 0,q = 0;
    Link(FindSet(a,p),FindSet(b,q));
}

int main()
{
	freopen("s.txt","r",stdin);
	int t;
	int n,m;
	char c;
	int x,y;
	int i,j;
	int p,q;

	scanf("%d",&t);
	while (t--)
	{
		scanf("%d%d",&n,&m);
		for (i=1; i<=n; i++)
			MakeSet(i);
        memset(w,0,sizeof(int)*(n+1));
		while (m--)
		{
			while (1)
			{
				scanf("%c",&c);
				if (c == 'A' || c == 'D')
					break;
			}
			scanf("%d%d",&x,&y);
			if (c == 'A')  //ask
			{
				p = q = 0;
				i = FindSet(x,p);
				j = FindSet(y,q);
				
				if (i != j)
					printf("Not sure yet.\n");
				else if ((p-q) % 2 == 0)
					printf("In the same gang.\n");
				else
					printf("In different gangs.\n");
			}
			else       //different
			{
				p = q = 0;
				i = FindSet(x,p);
				j = FindSet(y,q);
				
				if (i != j)
				{
					if ((p-q) % 2 == 0)
						adjust = 1;
					else
						adjust = 0;
					Union(i,j);
				}
			}
		}
	}
	return 0;
}

• 终于AC了。 (0) carew 2006-09-05 22:54:41