Luogu P1196 银河英雄传说

我们考虑用并查集来维护战舰的情况。

同时，我们用一个$d$数组来记录$x$与$fa[x]$之间的距离。再用$size$数组记录战舰当前所在列的战舰数。

易知两艘在同一列的战舰之间隔着$|d[x]-d[y]|-1$艘战舰。

#include<bits/stdc++.h>
#define N 30010using namespace std;int t,x,y;
int fa[N],d[N],size[N];
char op;int Find(int x) {
if(fa[x]==x) {
return x;
}
int root=Find(fa[x]);
d[x]+=d[fa[x]];
return fa[x]=root;
}void Init() {
for(int i=1;i<=30000;i++) {
fa[i]=i;
size[i]=1;
}
return;
}void Merge(int x,int y) {
int fx=Find(x),fy=Find(y);
d[fx]+=size[fy];
fa[fx]=fy;
size[fy]+=size[fx];
return;
}void Judge(int x,int y) {
int fx=Find(x),fy=Find(y);
if(fx==fy) {
printf("%d\n",abs(d[x]-d[y])-1);
}
else {
printf("-1\n");
}
return;
}void Work() {
cin>>op>>x>>y;
if(op=='M') {
Merge(x,y);
}
else if(op=='C') {
Judge(x,y);
}
return;
}int main()
{
Init();
scanf("%d",&t);
for(int i=1;i<=t;i++) {
Work();
}
return 0;
}