Posted on 2009-05-30 15:35
chenweiwei 阅读(276)
评论(0) 编辑 收藏 引用
Cube Stacking
Cube StackingFarmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.
Write a program that can verify the results of the game.
-------------------
仍然是并查，仍然是想了很久，仍然是参考了别人的代码才明白，学了这么久，真的会怀疑自己的智商了。
PKU1988仍然是并查的题目，没有特意说要找并查的题目来做，只是偶尔到了某一页发现某一道题目可以用并查来做，于是载下去了。
题意：
其实题意比较好理解，两个命令:如果是c命令则算出输出的cube X下面有多少个立方体，如果是M命令，则把cube Y所在的集合中的全部立方体放入cube X 所在的立方集合下。
初始化：
定义一个结构体，保存一个cube的根cube存于parent中，保存cube上面的立方数于up中，保存cube的下面的立方数于down中。
struct node
{
int parent;
int up;
int down;
}Node[SIZE];
void Init(int nt)
{
for (int i=0; i <= nt;i++)
{
Node[i].parent=i; //根为自己
Node[i].down=1; //初始化设为1只是为了计算的方便，到后面会减1
Node[i].up=0; //初始化高上面没有立方体。
}
}合并操作：
合并的时候找两个cube的根结点，并且对要结点的up及dow变量进行操作。具体看代码注释
int UnionSet(int i,int j)
{
i=FindSet(i);
j=FindSet(j);
Node[j].up=Node[i].down; //i下面的cube都变成了j上面的cube，归入Node[j].up
Node[i].down+=Node[j].down; //能够想像，j下面的所有cube同时也都归入i中
Node[j].parent=i; //两个集合合并成一个集合 i为根
return 0;
}
查询操作：
查询的时候找结点父亲，并且找父亲结点的上面cube数归入结点上面cube数中，如果父亲结点有根结点，则继续查找（哇，很难表达啊）。
int FindSet(int i)
{
int m;
if (Node[i].parent!=i)
{
m=Node[i].parent;
Node[i].parent=FindSet(Node[i].parent); //找父亲结点的父亲结点
Node[i].up+=Node[m].up; //将父亲结点的up归入结点的up中
}
return Node[i].parent;
}
主函数：
int main(int argc, char* argv[])
{
// freopen("in.txt","r",stdin);
int p;
scanf("%d",&p);
char op;
Init(SIZE);
while(p--)
{
getchar();
op=getchar();
if(op=='M')
{
int x,y;
scanf("%d %d",&x,&y);
UnionSet(x,y);
}
else if(op=='C')
{
int x,y;
scanf("%d",&x);
y=FindSet(x);
printf("%d\n",Node[y].down-Node[x].up-1); //这里需要减1
}
}
return 0;
}