AcWing 238. 银河英雄传说
原题链接
简单
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int f[N],d[N],Size[N];
int m;
int n;
int find(int x)
{
if(x!=f[x]){
int u=find(f[x]);
d[x]+=d[f[x]];
//因为一开始d[f[x]]不一定表示f[x]到根节点的距离,
//而find一遍后会更新,就表示的是到根节点的距离了
return f[x]=u;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=N;i++){
f[i]=i;Size[i]=1;
}
while(n--)
{
char op[2];
int x,y;
scanf("%s%d%d",&op,&x,&y);
if(op[0]=='M')
{
if(x==y)continue;
int a=find(x),b=find(y);
if(a==b) continue;
d[a]=Size[b];
Size[b]+=Size[a];
f[a]=b;
}
else
{
int a=find(x),b=find(y);
if(a!=b) puts("-1");
else printf("%d\n",max(0,abs(d[x]-d[y])-1));
}
}
return 0;
}
$\color{#FF00FF}{nb}$