记录编号	124371	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]银河英雄传说	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.598 s
提交时间	2014-10-03 15:13:11	内存使用	0.64 MiB

#include<cmath>
#include<cstdio> 
using namespace std;
char ch='A';
int x,y,t;
int f[30010],before[30010]={0},count[30010];
void merge(int,int);
void ask(int,int);
int find(int);
int main()
{
	freopen("galaxy.in","r",stdin);
	freopen("galaxy.out","w",stdout);
	scanf("%d",&t);
	for(int i=1;i<=30000;i++)
	{
		f[i]=i;
		count[i]=1;
	}
	for(int i=1;i<=t;i++)
	{
		scanf("%s%d%d",&ch,&x,&y);
		if(ch=='M') merge(x,y);
		if(ch=='C') ask(x,y);
	}
	return 0;
}
int find(int x)
{
	int fx;
	if(f[x]==x) return x;
	fx=find(f[x]);
	before[x]+=before[f[x]];
	f[x]=fx;
	return f[x];
}
void merge(int x,int y)
{
	int fx,fy;
	fx=find(x);
	fy=find(y);
	f[fx]=fy;
	before[fx]=count[fy];
	count[fy]+=count[fx];
}
void ask(int x,int y)
{
	if(find(x)!=find(y)) printf("-1\n");
	else 
	{
		int m=abs(before[x]-before[y])-1;
		printf("%d\n",m);
	}
}