[NOI2002]银河英雄传说

OI 题解 并查集

算法：并查集（带权）

代码分析：

带权并查集：

注意这个题要存每组的大小，因为题意是要合并到队列末端，而不是j的后面。

int fa[N], d[N], s[N];
//  父节点，到父节点的距离，每组的大小
int find(int x) {
    if(fa[x] == x) {
        return x;
    }
    int pre = fa[x];
    int ft = find(fa[x]);
    d[x] = d[pre] + d[x];//更新到父节点的距离（此时父节点是根节点）
    fa[x] = ft;
    return fa[x];
}
int main() {
    cin >> n;
    char op;
    int x, y;
    int ans, fx, fy;
    //初始化并查集
    for(int i = 1; i <= N; ++i) {
        fa[i] = i;
        s[i] = 1;
    }
    for(int i = 1; i <= n; ++i) {
        cin >> op >> x >> y;
        fx = find(x);
        fy = find(y);
        if(op == 'M') {
            if(fx != fy) {
                //合并
                fa[fx] = fy;   //直接合并到并查集根节点后
                d[fx] += s[fy];//但是距离依旧模拟合并到队列后边
                s[fy] += s[fx];
            }
        } else if(op == 'C') {
            if(fx != fy) {
                ans = -1;
            } else {
                ans = abs(d[x] - d[y]) - 1;//别忘了减一
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}