记录编号	224352	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]银河英雄传说	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.577 s
提交时间	2016-02-16 10:09:04	内存使用	0.64 MiB

#include<cstdio>
const int maxn = 30050;
int ufs[maxn],count[maxn],before[maxn];
int find(int x){
	if(x==ufs[x]){
		return x;
	}
	else{
		int newr = find(ufs[x]);
		before[x]+=before[ufs[x]];
		count[x]=count[ufs[x]];
		return ufs[x]=newr;
	}
}
void link(int ra,int rb){
	before[ra]=count[rb];
	count[rb]+=count[ra];
	ufs[ra]=rb;
}
bool linked(int a,int b){
	return find(a)==find(b);
}
int main(){
	freopen("galaxy.in","r",stdin);
	freopen("galaxy.out","w",stdout);
	int t,a,b;char tmp;scanf("%d",&t);
	for(int i = 1;i<=30050;++i){
		ufs[i]=i;
		count[i]=1;
		before[i]=0;
	}
	while(t--){
		tmp=getchar();
		tmp=getchar();
		scanf("%d %d",&a,&b);
		if(tmp=='M'){
			int r1=find(a),r2=find(b);
			link(r1,r2);
		}else if(tmp=='C'){
			if(!linked(a,b))printf("-1\n");
			else{
				if(before[a]>before[b])printf("%d\n",before[a]-before[b]-1);
				else printf("%d\n",before[b]-before[a]-1);
			}
		}
	}
	fclose(stdin);fclose(stdout);
	return 0;
}