银河英雄传说

银河英雄传说

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e4 + 10;
int t,a,b,fa[maxn],d[maxn],ssize[maxn];
//d表示与根节点的距离
//ssize表示根节点集合的大小
char ch;
int find(int x){
    if(x == fa[x]) return x;
    int root = find(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = root;
}
void merge(int x,int y){
    x = find(x);
    y = find(y);
    fa[x] = y;
    d[x] = ssize[y];
    ssize[y] += ssize[x];
}
int main(){
  // freopen("in","r",stdin);
    ios::sync_with_stdio(0);
    for(int i = 0; i < maxn; i++)
        fa[i] = i,ssize[i] = 1;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> ch >> a >> b;
        if(ch == 'M')
            merge(a,b);
        else {
            if (find(a) == find(b))
                cout << abs(d[b] - d[a]) - 1 << endl;
            else cout << "-1" << endl;
        }
    }
    return 0;
}