Pku1998并查集题解题报告.doc

Pku1998 Cube Stacking /* Name: pku1998 Copyright: ecjtu_acm Author: yimao Date: 22-08-10 09:19 Description: 并查集 */ 一、题目 DescriptionFarmer 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. Input * Line 1: A single integer, P * Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a M for a move operation or a C for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X. Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself. Output Print the output from each of the count operations in the same order as the input file. Sample Input 6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4Sample Output 1 0 2 二、题目大意及分析 【题意】 摘自《ACM程序设计竞赛入门》。 有n个独立的磁铁（1-n标号）放在桌上，一个人对这n堆进行移动操作，然后另一个人询问。规则： M： 将含有编号为X的磁铁放在包含Y的顶端上； C：询问在编号Z下面磁铁的数目； 【分析】 利用并查集，每一堆磁铁看作一个集合，“M a b”就是将a归并到b的上面，每个集合是有序的。设定3个域 Father： 根节点，初始化为本身； Num： 以该节点为根的集合的元素个数； Dis： 该点到其根的距离； 那么由num[father[a]]-dis[a]-1就是以a节点为根的集合所含有的元素个数。 三、代码及相关说明 /*1988 Accepted 736K 610MS G++ 1023B 2010-08-22 09:06:36 */ /*1988 Accepted 516K 297MS C++ 1023B 2010-08-22 09:07:03 */ #includestdio.h #define arr 30005 int father[arr],num[arr],dis[arr]; //查找根节点； int find(int x) { if(x!=father[x]) { int temp=father[x]; father[x]=find(father[x]); dis[x]