銀河英雄傳說
題目傳送門
解題思路
邊帶權的并查集
AC代碼
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int t,f[30005],num[30005],sum[30005];
int find(int x)//找爸爸
{
if(x==f[x])return x;
int xx=find(f[x]);
sum[x]+=sum[f[x]];
return f[x]=xx;
}
int main()
{
scanf("%d",&t);
for(int i=1;i<=30000;i++)f[i]=i,num[i]=1;
while(t--)
{
char ch;
int x,y;
cin>>ch;
scanf("%d%d",&x,&y);
int xx=find(x),yy=find(y);
if(ch=='M')//合并
{
sum[xx]+=num[yy];
f[xx]=yy;
num[yy]+=num[xx];
num[xx]=0;
}
else
{
if(xx!=yy)printf("-1\n");
else printf("%d\n",abs(sum[x]-sum[y])-1);
}
}
return 0;
}