传送门：238. 银河英雄传说 - AcWing题库

思路：
使用并查集可以传递关系的性质，维护一个cnt[i]数组，该数组用于记录以i为跟并查集树下的战舰的数量，用一个d[i]数组表示在i前面的战舰的数量。

d数组和cnt数组的维护可以在get函数和merge函数时实现。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=3e4+10;
int d[N],f[N],cnt[N];
int get(int x)
{if(x==f[x]) return x;int u=get(f[x]);d[x]+=d[f[x]];return f[x]=u;
}
void merge(int x,int y)
{x=get(x),y=get(y); //找到x，y分别所在队列的首节点战舰f[x]=y;d[x]=cnt[y];  //原本一个首节点前面的战舰数量是零，但是现在接在了y后面，所以要加上cnt【y】，x后面的节点的d值会在下一次有关查找时更新。cnt[y]+=cnt[x];    //因为是将x所在的队列接到y后面所以是y加上x
}
int main()
{int t;for(int i=1;i<=N;i++){f[i]=i;cnt[i]=1;//每艘战舰自身的便算一个//d[i]=1;  //这里不能初始化为1是因为一开始i前面的战舰的数量为零。}scanf("%d",&t);while(t--){char a[2];int b,c;scanf("%s%d%d",a,&b,&c);int   x=get(b),y=get(c);if(a[0]=='C'){if(x==y){printf("%d\n",max(0,abs(d[b]-d[c])-1));}elseputs("-1");}elseif(x!=y)merge(x,y);}return 0;
}