제목 설명

전송문

문제풀이의 방향

before는 i 앞에 몇 개의 원소가 있음을 표시하고,count[i]는 i가 있는 몇 개의 원소를 표시하며 수집한다.

코드

#include
#include
#include
#include
using namespace std;
int father[30005],before[30005],count[30005];
int n,i,x,y;
char z;
int find(int x){
	int f;
	if (father[x]==x) return father[x];
	f=find(father[x]);
	before[x]+=before[father[x]];
	father[x]=f;
	return father[x];
}
void merge(int x,int y){
	int i=find(x);
	int j=find(y);
	father[i]=j;
	before[i]+=count[j];
	count[j]+=count[i];
	return;
}
int main(){
	scanf("%d",&n);
	for (i=1;i<=30001;++i){
		father[i]=i;
		count[i]=1;
		before[i]=0;
	}
	for (i=1;i<=n;++i){
		cin>>z;
		cin>>x>>y;
		if (z=='M')
		  merge(x,y);
		if (z=='C')
		  if (find(x)!=find(y))
		    printf("-1
");
		  else
		    cout<<abs(before[x]-before[y])-1<<endl;
	}
	return 0;
}