Pku1998并查集题解题报告

《Pku1998并查集题解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Pku1998CubeStacking/*Name:pku1998Copyright:ecjtu_acmAuthor:yimaoDate:22-08-1009:19Description:并查集*/一、题目DescriptionFarmerJohnandBetsyareplayingagamewithN(1<=N<=30,000)identicalcubeslabeled1throughN.TheystartwithNstacks,eachcontainingasinglecube.FarmerJohnasksBetsytoperformP(1<=P<=100,000)ope

2、ration.Therearetwotypesofoperations:movesandcounts.*Inamoveoperation,FarmerJohnasksBessietomovethestackcontainingcubeXontopofthestackcontainingcubeY.*Inacountoperation,FarmerJohnasksBessietocountthenumberofcubesonthestackwithcubeXthatareunderthecubeXandreportthatvalue.Writeaprogramthatcanve

3、rifytheresultsofthegame.Input*Line1:Asingleinteger,P*Lines2..P+1:Eachoftheselinesdescribesalegaloperation.Line2describesthefirstoperation,etc.Eachlinebeginswitha'M'foramoveoperationora'C'foracountoperation.Formoveoperations,thelinealsocontainstwointegers:XandY.Forcountoperations,thelinealso

4、containsasingleinteger:X.NotethatthevalueforNdoesnotappearintheinputfile.Nomoveoperationwill4requestamoveastackontoitself.OutputPrinttheoutputfromeachofthecountoperationsinthesameorderastheinputfile.SampleInput6M16C1M24M26C3C4SampleOutput102二、题目大意及分析【题意】摘自《ACM程序设计竞赛入门》。有n个独立的磁铁（1-n标号）放在桌上，一

5、个人对这n堆进行移动操作，然后另一个人询问。规则：M：将含有编号为X的磁铁放在包含Y的顶端上；C：询问在编号Z下面磁铁的数目；【分析】利用并查集，每一堆磁铁看作一个集合，“Mab”就是将a归并到b的上面，每个集合是有序的。设定3个域Father：根节点，初始化为本身；Num：以该节点为根的集合的元素个数；Dis：该点到其根的距离；那么由num[father[a]]-dis[a]-1就是以a节点为根的集合所含有的元素个数。三、代码及相关说明/*1988Accepted736K610MSG++1023B2010-08-2209:06:36*//*1988Accepted516K2

6、97MSC++1023B2010-08-2209:07:03*/4#include#definearr30005intfather[arr],num[arr],dis[arr];//查找根节点；intfind(intx){if(x!=father[x]){inttemp=father[x];father[x]=find(father[x]);dis[x]+=dis[temp];}returnfather[x];}//把a放在b上面；father_b改变；voidunion_set(inta,intb){intf_a=find(a),f_b=find(b);f

7、ather[f_b]=f_a;dis[f_b]=num[f_a];num[f_a]+=num[f_b];}intmain(){intN,i,a,b;charch[3];while(scanf("%d",&N)!=EOF){for(i=1;i