题目描述：Cube Stacking (POJ 1988)
题目大意是有若干个立方体，每个立方体都有一个唯一的编号。这些立方体可以堆叠在一起，形成一个塔。每次操作可以选择一个立方体放在另一个立方体的上面。我们需要处理两种查询：
- 查询某个立方体所在塔的高度。
- 查询两个立方体是否在同一个塔中。
解题思路：
这个问题可以使用并查集（Union-Find）数据结构来解决。并查集是一种用于处理元素分组和合并的数据结构，特别适合解决动态连通性问题。
具体步骤：
-
初始化：
- 使用一个数组
parent来记录每个立方体的父节点。初始时，每个立方体都是自己的父节点。 - 使用一个数组
height来记录每个立方体所在塔的高度。初始时，每个立方体的高度为1。
- 使用一个数组
-
查找操作（Find）：
- 实现一个查找函数
find(x)，用于找到立方体x所在塔的根节点。在查找过程中，可以进行路径压缩，以优化后续的查找效率。
- 实现一个查找函数
-
合并操作（Union）：
- 实现一个合并函数
union(x, y)，用于将立方体x所在的塔放在立方体y所在的塔上面。合并时，需要更新塔的高度。
- 实现一个合并函数
-
查询高度：
- 直接返回
height[x]即可。
- 直接返回
-
查询是否在同一塔中：
- 使用
find(x)和find(y)查找两个立方体的根节点，如果根节点相同，则它们在同一塔中。
- 使用
代码实现：
#include
int parent[100001]; int height[100001];
int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 路径压缩 } return parent[x]; }
void unionSets(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { parent[rootX] = rootY; // 将x所在塔放在y所在塔上面 height[rootY] += height[rootX]; // 更新塔的高度 } }
int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) { parent[i] = i; height[i] = 1; }
char op;
int a, b;
while (cin >> op) {
if (op == 'M') {
cin >> a >> b;
unionSets(a, b);
} else if (op == 'Q') {
cin >> a;
cout << height[find(a)] << endl;
} else if (op == 'C') {
cin >> a >> b;
if (find(a) == find(b)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
}
return 0;}
解释：
-
初始化：
parent[i] = i表示每个立方体初始时都是自己的父节点。height[i] = 1表示每个立方体初始时的高度为1。
-
查找操作（Find）：
find(x)函数通过递归查找x的根节点，并进行路径压缩，以优化后续查找效率。
-
合并操作（Union）：
unionSets(x, y)函数首先找到x和y的根节点，然后将x所在塔放在y所在塔上面，并更新塔的高度。
-
查询高度：
- 直接输出
height[find(a)]，即a所在塔的高度。
- 直接输出
-
查询是否在同一塔中：
- 通过比较
find(a)和find(b)是否相同来判断a和b是否在同一塔中。
- 通过比较
通过上述步骤和代码实现，可以高效地解决 Cube Stacking 问题。