(54)-poj-Cube Stacking-参考3算法设计与分析

CubeStackingTimeLimit:

2000MS

MemoryLimit:

30000KTotalSubmissions:

18858

Accepted:

6547CaseTimeLimit:

1000MSDescriptionFarmerJohnandBetsyareplayingagamewithN(1<=N<=30,000)identicalcubeslabeled1throughN.TheystartwithNstacks,eachcontainingasinglecube.FarmerJohnasksBetsytoperformP(1<=P<=100,000)operation.Therearetwotypesofoperations:

movesandcounts.

*Inamoveoperation,FarmerJohnasksBessietomovethestackcontainingcubeXontopofthestackcontainingcubeY.

*Inacountoperation,FarmerJohnasksBessietocountthenumberofcubesonthestackwithcubeXthatareunderthecubeXandreportthatvalue.

Writeaprogramthatcanverifytheresultsofthegame.

Input*Line1:Asingleinteger,P

*Lines2..P+1:Eachoftheselinesdescribesalegaloperation.Line2describesthefirstoperation,etc.Eachlinebeginswitha'M'foramoveoperationora'C'foracountoperation.Formoveoperations,thelinealsocontainstwointegers:XandY.Forcountoperations,thelinealsocontainsasingleinteger:X.

NotethatthevalueforNdoesnotappearintheinputfile.Nomoveoperationwillrequestamoveastackontoitself.

OutputPrinttheoutputfromeachofthecountoperationsinthesameorderastheinputfile.

SampleInput6M16C1M24M26C3C4SampleOutput102题意：n个方块（n<=30000）,p组操作（p<=100000）,操作有两种，Mab将含有a的堆放在包含b的堆上，还有一种是Ca统计a下面有多少个方块思路：带权并查集，一堆中最顶上的方块作为父节点，用dist[X]统计X到父亲节点的距离，rank[fa[X]]表示团的大小，两者相减即为答案#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<string>#include<algorithm>#include<queue>usingnamespacestd;constintmaxn=30000+10;intfa[maxn];intrank[maxn];intdist[maxn];voidinit(){for(inti=0;i<maxn;i++){fa[i]=i;rank[i]=1;dist[i]=0;}}intfind(intx){if(x!=fa[x]){intt=fa[x];fa[x]=find(fa[x]);dist[x]+=dist[t];}returnfa[x];}intmain(){intn;while(~scanf("%d",&n)){init();charop;while(n--){cin>>op;inta,b;if(op=='M'){scanf("%d%d",&a,&b);intfaA=find(a);intfaB=find(b);if(faA!=faB){fa[faB]=faA;dist[faB]=rank[faA];rank[faA]+=rank[faB];}}else{scanf("%d