银河英雄传说

AcWing-238-银河英雄传说

分析

见《进阶指南》第196页。

实现

#include <iostream>
#define size SiZe
using namespace std;

const int N = 30010;
int f[N], d[N], size[N];

int find (int x) {
    if (f[x] == x) return x;

    int rt = find(f[x]);
    d[x] += d[f[x]];
    return f[x] = rt;
}
void merge (int x, int y) {
    int fx = find(x), fy = find(y);
    d[fx] = size[fy];
    size[fy] += size[fx];
    f[fx] = fy;
}
bool query (int x, int y) {
    return find(x) == find(y);
}

int main () {
    for (int i = 1; i <= 30000; ++ i) {
        f[i] = i;
        d[i] = 0;
        size[i] = 1;
    }
    int T;
    cin >> T;
    while (T --) {
        char opt;
        int i, j;
        cin >> opt >> i >> j;
        if (opt == 'M') {
            merge(i, j);
        } else {
            if (query(i, j) == true)
                cout << (i == j ? 0 : abs(d[j] - d[i]) - 1) << endl;
            else
                cout << -1 << endl;
        }
    }
    return 0;
}