边带权并查集,val[i]记录编号为i的舰船距离根舰船的距离,合并时如x接到y所在舰队的末尾,fx,fy为x,y的根节点,并不是val[fx] += val[y],这里的若不是真正舰队末尾则出错,需要sum[i]数组记录某一列舰队的数目,val[fx] += sum[fy];
具体如代码着重部分
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#pragma GCC optimize("O2")
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 30009
#define INF 1e18
#define mod 99999997
#define Pi acos(-1.0)
#define Pair pair<LL,LL>
#define eps 1e-9
LL n,m,k;
LL fa[MS];
LL val[MS]; // 编号为i的舰船距根节点距离
LL sum[MS]; // 记录第i列总舰数
LL find(LL x){
if(x != fa[x]){
LL t = fa[x];
fa[x] = find(fa[x]);
val[x] += val[t];
}
return fa[x];
}
void merge(LL x,LL y){
LL fx = find(x);
LL fy = find(y);
fa[fx] = fy;
/**********************/
val[fx] += sum[fy];
sum[fy] += sum[fx];
sum[fx] = 0;
/**********************/
}
int main(){
//ios::sync_with_stdio(false);
for(int i=1;i<=30000;i++) fa[i] = i ,sum[i] = 1;
cin >> k;
while(k--){
char op;
LL x,y;
cin >> op >> x >> y;
if(op == 'M'){
merge(x,y);
}
else{
if(find(x) != find(y)) printf("-1\n");
else{
LL t1 = val[x];
LL t2 = val[y];
printf("%lld\n",abs(t1-t2)-1);
}
}
}
return 0;
}