【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[]数组记录相对距离,并在合并时巧妙利用集合大小进行距离初始化。该解法不仅解决了“银河英雄传说”问题,也为其他涉及动态连通性查询的场景提供了优秀模板。建议读者深入理解路径压缩原理,并尝试优化其他类似问题,提升算法设计与实现能力。
原创内容 转载请注明出处