并查集求解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=30005;
int T;
int fa[N], sz[N], d[N]; // sz维护队列长度, d维护到队首的距离

inline int find(int x){
    if(x!=fa[x]){
        int root=find(fa[x]); // 递归查找根节点
        d[x]+=d[fa[x]];
        fa[x]=root;
    }
    return fa[x];
}

int main(){
    memset(d, 0x00, sizeof d);
    cin>>T;
    for(int i=1; i<N; ++i) {fa[i]=i; sz[i]=1;}
    while(T--){
        char ch;
        int x, y;
        cin>>ch>>x>>y;
        if(ch=='M'){ // 合并舰队
            int fx=find(x);
            int fy=find(y);
            d[fx]=sz[fy];
            sz[fy]+=sz[fx];
            fa[fx]=fy;
        }
        else if(ch=='C'){ // 查询舰队
            int fx=find(x);
            int fy=find(y);
            if(fx!=fy) cout<<-1<<endl;
            else cout<<max(0, abs(d[x]-d[y])-1)<<endl;
        }
    }

    return 0;
}