AcWing 238. 银河英雄传说

题目传送门

#include 

using namespace std;

const int N = 30010;

int p[N];  //并查集数组
int sz[N]; //家族中人员数量
int d[N];  //每个点到根节点的距离

//带边权更新并查集模板
int find(int x) {
    if (x == p[x]) return x;
    int root = find(p[x]);
    d[x] += d[p[x]];
    return p[x] = root;
}

int main() {
    int m;
    cin >> m;
    //初始化并查集，每个人是自己的族长，并且每个家族目前只有1个人
    for (int i = 1; i < N; i++) p[i] = i, sz[i] = 1, d[i] = 0;

    for (int i = 0; i < m; i++) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        int pa = find(a), pb = find(b);
        if (op == 'M') {
            d[pa] = sz[pb];   //记录pa到pb的距离，这和本题的摆法直接相关
            sz[pb] += sz[pa]; //家族人数增加sz[pa]
            p[pa] = pb;       // pa加入pb家族
        } else {
            //如果第 i 号战舰与第 j 号战舰当前不在同一列上，则输出 ?1。
            if (pa != pb)
                puts("-1");
            else                                              //如果两者相同，那么返回0
                printf("%d\n", max(0, abs(d[a] - d[b]) - 1)); //问间隔还需要减1
        }
    }

    return 0;
}