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. OutputPrint the output from each of the count operations in the same order as the input file. Sample Input6M 1 6C 1M 2 4M 2 6C 3C 4Sample Output102二、题目大意及分析【题意】摘自ACM程序设计竞赛入门。有n个独立的磁铁（1-n标号）放在桌上，一个人对这n堆进行移动操作，然后另一个人询问。规则：M： 将含有编号为X的磁铁放在包含Y的顶端上；C：询问在编号Z下面磁铁的数目；【分析】利用并查集，每一堆磁铁看作一个集合，“M a b”就是将a归并到b的上面，每个集合是有序的。设定3个域Father： 根节点，初始化为本身；Num： 以该节点为根的集合的元素个数；Dis： 该点到其根的距离；那么由numfathera-disa-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 */#include#define arr 30005int fatherarr,numarr,disarr;/查找根节点；int find(int x) if(x!=fatherx) int temp=fatherx; fatherx=find(fatherx); disx+= distemp; return fatherx; /把a放在b上面；father_b改变；void union_set(int a,int b) int f_a=find(a),f_b=find(b); fatherf_b=f_a; disf_b=numf_a; numf_a+= numf_b;int main() int N,i,a,b; char ch3; while(scanf(%d,&N)!=EOF) for(i=1;iarr;i+) fatheri=i,numi=1,disi=0; /上面写i=N就Runtime Error； for(i=1;i=N;i+) scanf(%s,ch); i