A0944 [NOI2002] 银河英雄传说

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30000;

int fa[MAXN + 1];   // 并查集父节点（每个集合的根是这一列的队首）
int sz[MAXN + 1];   // 以根为队首的列里有多少艘战舰
int off[MAXN + 1];  // 战舰到其父节点的位置差：pos(x) - pos(fa[x])

// 路径压缩，同时把位置差累加起来
int find(int x) {
    if (fa[x] == x) return x;
    int t = fa[x];
    fa[x] = find(t);
    off[x] += off[t];
    return fa[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 1; i <= MAXN; i++) {
        fa[i] = i;
        sz[i] = 1;
        off[i] = 0;
    }

    int T;
    cin >> T;
    while (T--) {
        char op;
        int i, j;
        cin >> op >> i >> j;
        if (op == 'M') {
            // 第 i 号所在队列，整体接到第 j 号所在队列的尾部
            int ri = find(i);
            int rj = find(j);
            if (ri != rj) {
                fa[ri] = rj;
                off[ri] = sz[rj];   // i 队列的队首排在 j 队列队首之后 sz[rj] 个位置
                sz[rj] += sz[ri];
            }
        } else {
            // 询问两艘战舰之间夹着多少艘
            int ri = find(i);
            int rj = find(j);
            if (ri != rj) {
                cout << -1 << '\n';
            } else {
                cout << abs(off[i] - off[j]) - 1 << '\n';
            }
        }
    }
    return 0;
}