HDU-2818-Building Block

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=2818

Building Block

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

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

Sample Output

1
0
2
        

題目分析：帶權并查集  

n塊磚頭，分為n堆，有兩種操作M：把x堆放在y堆上面，C：求x堆的下面有多少個磚頭。在普通并查集的基礎上加上兩個數組up[x]和down[x]，分别表示x所在堆的大小以及x下面的元素。當移動時，首先确定x所在的那一堆最底部的X以及y所在那一堆最底部的Y，那麼down[X]的數目就是另外一堆的up[Y]，可以根據find（x）遞歸去一邊尋找根一邊更新其他未知的down[x]，。

代碼如下：

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio> 
using namespace std;
int city,road;
int pre[33333];
int up[33333],down[33333];
int find(int r)
{
    if(pre[r]==r)
    return r;
    else
    {
        int t=find(pre[r]);
        down[r]=down[r]+down[pre[r]];
        pre[r]=t; 
        return pre[r];
    }
}
void merge(int x,int y)
{
    int t1=find(x);
    int t2=find(y);
    if(t1!=t2)
    {
        pre[t1]=t2;
        down[t1]=up[t2];
        up[t2]+=up[t1];
    }
}
int main(){
	int n;
	while(cin>>n)
	{
		int i;
        char str[11];
        int x,y;
        for(i=0;i<=30010;i++)//否則會逾時 
        {
        	pre[i]=i;
        	up[i]=1;//以上的部分包括自己 
            down[i]=0;//下面的數量 
		}
		for(i=1;i<=n;i++)
		{
			cin>>str;
			if(str[0]=='M')
			{
				scanf("%d%d",&x,&y);
				merge(x,y);
			}
			else
			{
				scanf("%d",&x);
				find(x);
				cout<<down[x]<<endl;
			}
		}
	}
	return 0;
}