P1196 [NOI2002]银河英雄传说

Link

题解

带权并查集

代码

#include <algorithm>
#include <iostream>
const int maxn = 30000 + 10;
using namespace std;

int fa[maxn], dis[maxn], sz[maxn];

void init(int n) {
    for (int i = 1; i <= n; i++)fa[i] = i;
    for (int i = 1; i <= n; i++)dis[i] = 0;
    for (int i = 1; i <= n; i++)sz[i] = 1;
}

int findr(int x) {
    if (fa[x] == x)return x;
    else {
        int f = fa[x];
        fa[x] = findr(fa[x]);
        dis[x] += dis[f];
        sz[x] = 0;
        return fa[x];
    }
}

void merge(int x, int y) {
    int xr = findr(x);
    int yr = findr(y);
    if (xr != yr) {
        fa[xr] = yr;
        dis[xr] = dis[yr] + sz[yr];
        sz[yr] += sz[xr];
        sz[xr] = sz[yr];
    }
}

int cal(int u, int v) {
    int ur = findr(u);
    int vr = findr(v);
    if (ur != vr)return -1;
    else return abs(dis[u] - dis[v]) - 1;
}

int main() {
    init(30000);
    int t, u, v;
    char o;
    cin >> t;
    while (t--) {
        cin >> o >> u >> v;
        if (o == 'M')merge(u, v);
        else cout << cal(u, v) << endl;
    }
    return 0;
}