学步园

曾经写过一遍，不过这次似乎写得更加顺畅。

注意10^5,是多大……我竟然把MAX_SIZE定义小了一个数量级==！

/*
 * find them, catch them
 * mike-w
 * 2012-4-28
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 123456

int T,N,M;
int diff[MAX_SIZE];
int set[MAX_SIZE],rank[MAX_SIZE];

int set_init(int size)
{
	int i;
	for(i=1;i<=size;i++)
		set[i]=i,rank[i]=1;
	return 0;
}

int set_find(int e)
{
	if(set[e]==e)
		return e;
	else
		return set[e]=set_find(set[e]);
}

int set_merge(int e1, int e2)
{
	int r1=set_find(e1);
	int r2=set_find(e2);
	if(r1==r2)
		return -1;
	if(rank[r1]<rank[r2])
		set[r1]=r2;
	else if(rank[r1]>rank[r2])
		set[r2]=r1;
	else
		set[r1]=r2,rank[r2]++;
	return 0;
}

int main(void)
{
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
#endif
	int r1,r2,c1,c2;
	char buf[5];
	const char str_same[]="In the same gang.";
	const char str_diff[]="In different gangs.";
	const char str_not_sure[]="Not sure yet.";
	scanf("%d",&T);
	while(T-->0)
	{
		scanf("%d%d",&N,&M);
		memset(diff,0,sizeof(diff));
		set_init(N);
		if(N==2)
			diff[1]=2;
		while(M-->0)
		{
			scanf("%s%d%d",buf,&c1,&c2);
			if(buf[0]=='A')
			{
				if(c1<=N && c2<=N)
					r1=set_find(c1), r2=set_find(c2);
				else
					r1=r2=0;
				if(r1==r2)
					puts(str_same);
				else if(set_find(diff[r1])==r2)
					puts(str_diff);
				else
					puts(str_not_sure);
			}
			else
			{
				if(!diff[c1])
					diff[c1]=c2;
				else
					set_merge(diff[c1],c2);
				if(!diff[c2])
					diff[c2]=c1;
				else
					set_merge(diff[c2],c1);
			}
		}
	}
	return 0;
}