AcWing 238. 银河英雄传说
原题链接
简单
作者:
uhhh
,
2021-03-14 22:14:39
,
所有人可见
,
阅读 278
//并查集距离维护祖先结点深度
#include<bits/stdc++.h>
#define N 30010
using namespace std;
int fa[N],d[N],s[N];
void init(){
for(int i=1;i<N;i++){
fa[i]=i;
d[i]=0;
s[i]=1;
}
}
int find(int x)
{
if(fa[x]!=x)
{
int root=find(fa[x]);
d[x]+=d[fa[x]];
fa[x]=root;
}
return fa[x];
}
int main(){
int n;
init();
scanf("%d",&n);
for(int i=0;i<n;i++){
int a,b;
char m[2];
scanf("%s %d %d",m,&a,&b);
int pa=find(a),pb=find(b);
if(m[0]=='M'){
if(pa!=pb)
{
fa[pa]=pb;
d[pa]=s[pb];
s[pb]+=s[pa];
}
}
else{
if(pa==pb) printf("%d\n",max(abs(d[a]-d[b])-1,0));
else printf("-1\n");
}
}
return 0;
}