题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2818
题目大意：每次指定一块砖头，移动砖头所在堆到另一堆。查询指定砖头下面有几块砖头。
解题思路：
【HDU数据有问题】，数据从0开始，且给定n块砖头（比如1000），数据会有第1005块砖头，导致访问越界。
【解决方案】，并查集初始化范围改为0~maxn(30005)
由于只给定一块砖头，却要移动所在堆。所以需要并查集维护所在堆。
p[x]=y，即x所在堆的堆底是y，注意此时并查集是有方向的。
用under[x]维护x下面有几块砖头，sum[x]维护x所在堆一共有几块砖头。
对于移动x堆到y堆，首先对x和y的堆底两点处理，合并后，X堆、Y堆所有点的堆底都指向Y堆的堆底：
①获取x和y所在堆的堆底，即X=find(x)，Y=find(y)
②under[X]=sum[Y]，即合并后，X堆下面有Y堆总个数
③sum[Y]+=sum[X]，由于合并后，两堆结点在路径压缩时会集体更新，所以这里只要令sum[Y]=两堆和就可以了。
③f[X]=Y,让X堆的堆底都指向Y堆堆底。
路径压缩部分:
①under[x]+=under[f[x]]，即原X堆堆底以上的under，全部加上堆底under（堆底已经被手动更新）。
②f[x]=find(f[x])，堆底以上的指向更新。
#include "cstdio"
#define maxn 30005
int f[maxn],under[maxn],sum[maxn];
int find(int x)
{
if(x!=f[x])
{
int t=find(f[x]);
under[x]+=under[f[x]];
return f[x]=t;
}
else return x;
}
void Union(int x,int y)
{
x=find(x),y=find(y);
if(x!=y)
{
under[x]=sum[y];
sum[y]+=sum[x];
f[x]=y;
}
}
int main()
{
//freopen("in.txt","r",stdin);
int n,x,y;
char cmd;
scanf("%d",&n);
for(int i=;i<maxn;i++)
{
f[i]=i;
sum[i]=;
}
for(int i=;i<=n;i++)
{
getchar();
scanf("%c",&cmd);
if(cmd=='M')
{
scanf("%d%d",&x,&y);
Union(x,y);
}
else
{
scanf("%d",&x);
find(x);
printf("%d\n",under[x]);
}
}
}