﻿HDU 2818 Building Block(带权并查集)-Ocrosoft

# Building Block

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

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

```

Solution

M a b 表示将包含a的方块放到包含b方块上（都是往上放的）。

C a 是询问a的方块下面有多少方块（不含a）。

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 30000+10
using namespace std;
int pre[MAXN],r[MAXN],m[MAXN];
int find(int x)
{
if(pre[x]!=x)
{
int p=pre[x];
pre[x]=find(p);
r[x]+=r[p];
}
return pre[x];
}
void Union(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
{
pre[fx]=fy;
r[fx]+=m[fy]+1;
m[fy]+=m[fx]+1;
}
}
void init()
{
ms(r),ms(m);
for(int i=0; i<MAXN; i++)pre[i]=i;
}
int main()
{
int n,a,b;
char c;
while(cin>>n)
{
init();
while(n--)
{
cin>>c;
if(c=='M')
{
int a,b;
cin>>a>>b;
Union(a,b);
}
else
{
cin>>a;
find(a);
printf("%d\n",r[a]);
}
}
}
return 0;
}```