记录编号	340885	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]银河英雄传说	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.698 s
提交时间	2016-11-07 07:26:17	内存使用	0.64 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=30010;
int findroot(int);
void mergeset(int,int);
int m,prt[maxn],size[maxn],dis[maxn]={0},x,y;
char c;
int main(){
#define MINE
#ifdef MINE
	freopen("galaxy.in","r",stdin);
	freopen("galaxy.out","w",stdout);
#endif
	for(int i=1;i<=30000;i++){
		prt[i]=i;
		size[i]=1;
	}
	scanf("%d",&m);
	while(m--){
		scanf(" %c%d%d",&c,&x,&y);
		if(c=='M')mergeset(x,y);
		else{
			if(findroot(x)!=findroot(y))printf("-1\n");
			else printf("%d\n",abs(dis[x]-dis[y])-1);
		}
	}
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}
int findroot(int x){
	if(prt[x]!=x){
		int p=prt[x];
		prt[x]=findroot(prt[x]);
		dis[x]+=dis[p];
	}
	else dis[x]=0;
	return prt[x];
}
void mergeset(int x,int y){//把x接到y上
	x=findroot(x);
	y=findroot(y);
	if(x==y)return;
	prt[x]=y;
	dis[x]=size[y];
	size[y]+=size[x];
}