hdu 2818 Building Block

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2818

分析：带权并查集，给出两种操作，分别是并和查。 不过合并方式并不相同，要求将x中的元素合并到y中。

/*Building Block

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3484    Accepted Submission(s): 1047


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
 

Source
2009 Multi-University Training Contest 1 - Host by TJU
 
*/
#include <cstdio>
#include <cstring>
const int maxn = 30000 + 100; 
/*
 markset()用以初始化
 findset()查询
 unin() 合并 
*/ 
struct lset{
    int p[maxn], rank[maxn], sum[maxn], sz;  
    void makeset()
    {
        memset(rank, 0, sizeof(rank));
        memset(sum, 0, sizeof(sum));
        for(int i = 0; i < maxn; i++){
            p[i] = i;  
        }
    }
    int findset(int x)
    {
        if(x != p[x]){
            int fa = p[x];
            p[x] = findset(fa);
            rank[x] += rank[fa];
        }
        return p[x];
    }
    void unin(int x, int y)
    {
        int fx = findset(x), fy = findset(y);
        if(fx != fy){
            p[fx] = fy;
            rank[fx] += sum[fy] + 1;
            sum[fy] += sum[fx] + 1;
        } 
    }
    void compress()
    {
        for(int i = 0; i < sz; i++) findset(i);
    }
};

int main()
{
    int p, x, y;
    char c;
    lset B;
    while(~scanf("%d%*c", &p)){
        B.makeset();
        for(int i = 0; i < p; i++){
            c = getchar();
            if(c == 'M'){
                scanf("%d%d%*C", &x, &y);
                B.unin(x, y);
            }
            else{
                scanf("%d%*C", &x);
                B.findset(x);
                printf("%d
", B.rank[x]);
            }
        }
    }
    return 0;
}