【NOI 2002】银河英雄传说（洛谷P1196）题解：并查集优化路径压缩算法详解

一、题目解读

“银河英雄传说”是一道经典的动态集合合并问题。题目背景设定在星际战争中，要求处理两种指令：战舰合并（M）和距离查询（C）。需要维护多个战舰集合，支持快速合并操作，并计算同一集合内任意两战舰的距离。核心挑战在于高效处理大规模数据与动态变化，避免时间复杂度爆炸。

二、解题思路

采用并查集（Union-Find）算法解决该问题。关键在于设计三个核心数组：

1. parent[]：记录每个战舰的父节点，实现集合划分；

2. dist[]：存储每个节点到父节点的距离，用于距离累加；

3. size[]：维护集合大小，辅助合并时的距离计算。

通过路径压缩与距离更新，将查询与合并的时间复杂度优化至近乎O(α(n))（α为阿克曼函数的反函数，实际接近常数）。

三、解题步骤

1. 初始化：每个战舰自成集合，父节点指向自身，距离与大小初始化为0和1。

2. 处理合并指令（M）：

    找到两战舰的根节点；

    将较小集合的根节点连接到较大集合，更新距离与集合大小。

3. 处理距离查询指令（C）：

    若两战舰根节点不同，则不在同一列，输出-1；

    若在同一列，通过路径压缩后的距离差计算实际距离（需考虑边界修正）。

4. 路径压缩优化：在查找根节点时，递归过程中将路径上所有节点直接连接到根节点，减少后续查询深度。

四、代码与注释

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAXN = 30010;  // 最大战舰数量

int parent[MAXN];  // 父节点数组
int dist[MAXN];    // 到父节点的距离
int size[MAXN];    // 集合大小

// 初始化并查集
void init() {
    for (int i = 1; i < MAXN; i++) {
        parent[i] = i;      // 每个节点初始为根节点
        dist[i] = 0;        // 初始距离为0
        size[i] = 1;        // 集合大小为1
    }
}

// 查找根节点，路径压缩+距离更新
int find(int x) {
    if (parent[x]!= x) {  // 若x非根节点
        int root = find(parent[x]);  // 递归查找根节点
        dist[x] += dist[parent[x]];  // 累加路径上所有距离
        parent[x] = root;            // 直接连接x到根节点
    }
    return parent[x];
}

// 合并集合x和y
void merge(int x, int y) {
    int rootX = find(x);  // 找到x的根节点
    int rootY = find(y);  // 找到y的根节点
    if (rootX!= rootY) {  // 若不在同一集合
        parent[rootX] = rootY;          // 将x的根连接到y的根
        dist[rootX] = size[rootY];      // 更新距离：x根到新根的距离为y集合大小
        size[rootY] += size[rootX];     // 合并集合大小
    }
}

int main() {
    ios::sync_with_stdio(false);  // 加快IO速度
    cin.tie(nullptr);
    
    init();  // 初始化并查集
    
    int T;  // 指令总数
    cin >> T;
    while (T--) {
        char op;  // 指令类型
        int i, j;  // 战舰编号
        cin >> op >> i >> j;
        if (op == 'M') {
            merge(i, j);  // 执行合并
        } else {
            int rootI = find(i);  // 查找i的根节点
            int rootJ = find(j);  // 查找j的根节点
            if (rootI!= rootJ) {
                cout << -1 << "\n";  // 不同集合，输出-1
            } else {
                // 计算距离：dist[i]-dist[j]的绝对值-1（修正路径压缩导致的误差）
                int ans = abs(dist[i] - dist[j]) - 1;
                cout << (ans < 0? 0 : ans) << "\n";  // 确保结果非负
            }
        }
    }
    return 0;
}

五、总结

本代码通过并查集实现了高效的动态集合管理，利用路径压缩大幅降低查询与合并的时间成本。关键在于通过dist[]数组记录相对距离，并在合并时巧妙利用集合大小进行距离初始化。该解法不仅解决了“银河英雄传说”问题，也为其他涉及动态连通性查询的场景提供了优秀模板。建议读者深入理解路径压缩原理，并尝试优化其他类似问题，提升算法设计与实现能力。