题解 | #银河英雄传说#

思路

并查集 即可 .
问题在于如何 求两个战舰之间的 战舰数目 ?

我们使用 d[ ] 和 num[ ]来辅助我们解决上面的问题
d[i]：i 距离根节点（队头）的距离
num[i]：i 所在的连通块有多少个元素（ i 所在那一列的战舰数目 ）

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 30010;

int d[N],num[N];
int fa[N];

int find(int x){
    if(x==fa[x]) return x;
    int root=find(fa[x]);
    d[x]+=d[fa[x]];
    fa[x]=root;
    return root;
}

int main(){
    int T; scanf("%d",&T);
    for(int i=1;i<=30000;i++) fa[i]=i,num[i]=1;
    while(T--){
        char c[2];
        int x,y;
        scanf("%s%d%d",c,&x,&y);
        if(c[0]=='M'){
            x=find(x),y=find(y);
            if(x!=y){
                fa[x]=y;
                d[x]=num[y];
                num[y]+=num[x];
            }
        }
        else {
            int fx=find(x),fy=find(y);
            if(fx!=fy) puts("-1");
            else if(x==y) puts("0");
            else printf("%d\n",abs(d[x]-d[y])-1);
        }
    }
    return 0;
}