Building Block

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 15 Accepted Submission(s) : 4

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

John are playing with blocks. There are N blocks (1 <= N <= 30000) numbered 1...N。Initially, there are N piles, and each pile contains one block. Then John do some operations P times (1 <= P <= 1000000). There are two kinds of operation:

M X Y : Put the whole pile containing block X up to the pile containing Y. If X and Y are in the same pile, just ignore this command.

C X : Count the number of blocks under block X

You are request to find out the output for each C operation.

Input

The first line contains integer P. Then P lines follow, each of which contain an operation describe above.

Output

Output the count for each C operations in one line.

Sample Input

6M 1 6C 1M 2 4M 2 6C 3C 4

Sample Output

Source

2009 Multi-University Training Contest 1 - Host by TJU

题目大意：第一行输入P，表示有P个积木和P次操作，编号可能从0~N。

　　刚开始积木的状态是：每个编号独自算作一个集合。

　　然后下面有P行，每一行输入操作指令：

　　　　M a,b,表示吧包含编号a的集合放在包含编号b集合的上面、

　　　　c a，表示询问编号a下面有多少个积木、

解法一：（并查集+压缩路径）

　　用Count[i]记录以i为根子节点的积木总数，,即为包含编号i的积木总数，记录子节点和父节点。

　　每次进行M a b操作时：

　　　　用A=Find(a),B=Find(b)查找子根节点，且合并子节点。

　　　　在去找B的父节点，更新B的父根节点。同时，更新每一个节点上的积木总数。

　　在进行C a操作时：

　　　　查找a的根子节点aa=Find(a)，

　　　　输出count[aa]-count[a]即为答案、

解法二：

　　多增加了一个记录状态的数组，Dowm[i]是用来记录i下方有多少个积木。

　　而且，只需要记录子节点即可。Find(x)用来查找子节点和更新Dowm[]

　每次进行M a b操作时：

　　　　用A=Find(a),B=Find(b)查找子根节点，且合并子节点。ID[a]=b;

　　　　Dowm[a]=Count[b];/*Dowm[a]更新为集合b的数量*/

Count[b]+=Count[a];/*同时，连接两个集合，更新集合总数*

　　在进行C a操作时：

　　　　只需要调用Find(x)即可更新Dowm[a]，输出Dowm[a]即可。

1 #include 
        
          2 #include 
         
           3 #include 
          
            4 #include 
            5 using namespace std; 6 int Count[333333],ID[333333]; 7 int ID_S[333333]; 8 void Cread_(int N) 9 {10     for(int i=0;i<=N;i++)11     {12         Count[i]=1;13         ID[i]=i;14         ID_S[i]=i;15     }16 }17 int Find_Son(int x)18 {19     int tmp,p=x;20     if(ID[x]!=x)21         tmp=Find_Son(ID[x]);22     else {tmp=x;};23     ID[x]=tmp;24     return tmp;25 }26 27 int Find_Far(int x,int sum)28 {29     while(ID_S[x]!=x)30     {31         Count[x]+=sum;32         x=ID_S[x];33     }34     Count[x]+=sum;35     return x;36 }37 38 int main()39 {40     int T,i,j,k,a,aa,b,A,B;41     char str;42     scanf("%d",&T);43     Cread_(T);44     while(T--)45     {46 47         scanf(" %c",&str);48         if(str=='M')49         {50             scanf("%d%d",&a,&b);51             a=Find_Son(a);52             b=Find_Son(b);53             if(a!=b)54             {55                 ID[a]=b;56                 aa=Find_Far(b,Count[a]);57                 ID_S[aa]=a;58             }59         }60         else61         {62             scanf("%d",&a);63             aa=Find_Son(a);64             printf("%d\n",Count[aa]-Count[a]);65         }66     }67     return 0;68 }

解法一

修改：2015.5.31

1 #include 
        
          2 #include 
         
           3 #include 
          
            4 #include 
            5 using namespace std; 6 int Count[301000];/*Count[i]表示包含编号i的积木总数,即为以i为根节点的积木数*/ 7 int ID[301000];   /*ID[i]=j*表示i指向j，i在j的上方*/ 8 int Dowm[301000];/*Dowm[i]记录i下方有多少个积木*/ 9 void Cread_(int N)/*初始化*/10 {11     for(int i=0;i<=N;i++)12     {13         Count[i]=1;/*刚开始独自一个一堆*/14         ID[i]=i;/*指向自己表示单体*/15         Dowm[i]=0;/*刚开始下方都没有积木*/16     }17 }18 int Find_Son(int x)/*寻找x的根子节点，并且更新路径上的Dowm[i]*/19 {20     int tmp,p=x;21     if(ID[x]!=x)22     {23         tmp=Find_Son(ID[x]);    /*递归获取根子节点*/24         Dowm[x]+=Dowm[ID[x]];   /*更新，类似于记忆化搜索*/25     }26     else tmp=x;27     ID[x]=tmp;  /*压缩路径，与更新并不矛盾*/28     return tmp;29 }30 31 int main()32 {33     int T,i,j,k,a,aa,b,A,B;34     char str;35     scanf("%d",&T);36     Cread_(T);37     while(T--)38     {39 40         scanf(" %c",&str);41         if(str=='M')42         {43             scanf("%d%d",&a,&b);44             a=Find_Son(a);/*寻找a根节点*/45             b=Find_Son(b);/*寻找b根节点*/46             if(a!=b)47             {48                 ID[a]=b;    /*把b放在a的下方*/49                 Dowm[a]=Count[b];/*Dowm[a]更新为集合b的数量*/50                 Count[b]+=Count[a];/*同时，连接两个集合，更新集合总数*/51             }52         }53         else54         {55             scanf("%d",&a);56             Find_Son(a);/*寻找a的根节点同时更新Dowm[a]*/57             printf("%d\n",Dowm[a]);58         }59     }60     return 0;61 }