Skip to main content

238.银河英雄传说

tip

原题链接：https://www.acwing.com/problem/content/240/

思路​

  • 本质上是一个带深度和集合大小的带权并查集问题

  • 本题中深度表示相隔的战舰数量，集合大小表示所在列中有多少战舰

  • 当执行 M 指令时，第 j 号战舰所在列要接上战舰 i 所在的列，即 p[find(i)] = find(j); d[find(j)]的深度就要加上战舰 i 所在列的大小，即 d[find(j)] += s[find(i)]; 接上之后，战舰j所在列集合大小要变，s[find(j)] += s[find(i)];

  • 当执行 C 指令时，通过find找到 i 和 j 是否在同一个集合，间隔战舰数量就是通过 d 计算，abs(d[i]-d[j]-1)就是距离

代码​

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

using namespace std;

const int N = 3e4 + 10;

int t;
int p[N], d[N], s[N];

int find(int x) {
    if (p[x] != x) {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main() {
    cin >> t;

    for (int i = 1; i <= N; i++) {
        p[i] = i;
        s[i] = 1;
        d[i] = 0;
    }

    while (t --) {
        char ops;
        cin >> ops;

        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if (ops == 'M') {
            p[pa] = pb;
            d[pa] += s[pb];
            s[pb] += s[pa];
        } else {
            if (pa == pb) {
               cout << max(abs(d[b] - d[a]) - 1, 0) << endl;
            } else {
                cout << -1 << endl;
            }
        }
    }
    return 0;
}