【NOI 2002】银河英雄传说（洛谷P1196）题解：并查集优化路径压缩算法详解
2天前
一、题目解读
“银河英雄传说”是一道经典的动态集合合并问题。题目背景设定在星际战争中，要求处理两种指令：战舰合并（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[]数组记录相对距离，并在合并时巧妙利用集合大小进行距离初始化。该解法不仅解决了“银河英雄传说”问题，也为其他涉及动态连通性查询的场景提供了优秀模板。建议读者深入理解路径压缩原理，并尝试优化其他类似问题，提升算法设计与实现能力。
原创内容 转载请注明出处
