首页 > 代码库 > POJ1988 CubeStacking (并查集)
POJ1988 CubeStacking (并查集)
本文出自:http://blog.csdn.net/svitter
题意:
开始有N堆方块,编号从1~n。每次移动一堆方块,最后求某个方块下面方块的个数。
输入输出分析:
开始输入一个数字P,代表输入操作个数。
此处发现在g++4.8的版本中,类似与 char ch[0]这样的数组也是可以开辟的。。。
一个不小心开辟了这样一个数组。。然后return 0完全找不到错误所在。。
随后的2~1+p行,每行一组操作数据。
M i j代表移动i的堆到j的堆上。
C i代表求出i以下的方块个数。
数据结构算法分析:
本题目使用并查集来进行计算。
sum[n]数组来统计当前堆n中方块个数。
under[n]数组来统计当前n下面的方块个数。
在进行计算的时候,路径压缩和合并均更新under的值。
未进行路径压缩的时候,方块n所记录的under并非final value, 仅仅只是包含了到root[n]的方块个数。
通过路径压缩的过程,不断的增加当前n的根节点(递归)的under值,求出最终的under值
进行路径合并的时候,更新sum值和under值。当一个堆放在另一个堆上时,被移动的堆的under值一定为0,
此时更新under值为另一个堆的根的sum值,即计算出了此处的部分under值。然后更新合并堆的sum值。
AC代码:
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; const int MAXN = 30010; int root[MAXN]; int under[MAXN]; int sum[MAXN]; void init() { for(int i = 0; i < MAXN; i++) { root[i] = i; under[i] = 0; sum[i] = 1; } } int getRoot(int i) { if(i == root[i]) return i; int t = getRoot(root[i]); under[i] += under[root[i]]; root[i] = t; return root[i]; } int a,b; void Merge(int i, int j) { a = getRoot(i); b = getRoot(j); if(a == b) return; root[a] = b; under[a] = sum[b]; sum[b] += sum[a]; } int main() { int p; char ch[0]; int t1, t2; init(); scanf("%d", &p); while(p--) { scanf("%s", ch); if(ch[0] == 'M') { scanf("%d", &t1); scanf("%d", &t2); Merge(t1, t2); } else { scanf("%d", &t1); getRoot(t1); printf("%d\n", under[t1]); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。