记录编号	127520	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]银河英雄传说	最终得分	100
用户昵称	ok	是否通过	通过
代码语言	C++	运行时间	2.996 s
提交时间	2014-10-15 20:25:05	内存使用	0.66 MiB

#include <fstream>
using namespace std;
ifstream input("galaxy.in");
ofstream output("galaxy.out");
int p[30003]={0},n,le[30003]={0},ri[30003]={0};
int find(int x)
{
	int mm;
	if(x!=p[x])
	{
		mm=p[x];
		p[x]=find(p[x]);
		le[x]+=le[mm];
	}
	return p[x];
}
int main()
{
	int i,b,c;
	char a;
	int bb,cc;
	input>>n;
	for(i=1;i<=30000;i++)
	{
		ri[i]=1;
		p[i]=i;
	}
	for(i=1;i<=n;i++)
	{
		input>>a>>b>>c;
		if(a=='M')
		{
			bb=find(b);
			cc=find(c);
			if(bb!=cc)
			{
				p[bb]=cc;
				le[bb]=ri[cc];
				ri[cc]+=ri[bb];
			}
		}
		else
		{
			int z;
			if(find(b)!=find(c)) output<<"-1"<<endl;
			else
			{
				z=le[b]-le[c];
				if(z>0) output<<z-1<<endl;
				else
				{
					z=-1*z-1;
					output<<z<<endl;
				}
			}
		}
	}
	input.close();
	output.close();
	return 0;
}