poj1988 266ms 并查集

#include<cstdio>
using namespace std;
//说难不难，说简单不简单，就是并查集的处理，额外的两个数组是关键
//解决并查集有关问题时，如何利用辅助数组记录节点与根节点的关系是解题的关键
const int N = 3e4;
int father[N+5],under[N+5],sum[N+5];
//parent[i]=i,sum[i]表示砖块i所在堆的砖块数目，under[i]表示砖块i下面有多少砖块
void init(int n)
{
    for(int i = 1; i<=n; ++i)
    {
        father[i] = i;
        sum[i] = 1;
        under[i] = 0;
    }
}
int find(int x)
{
    if(x!=father[x])
    {
        int px = find(father[x]);
        under[x] += under[father[x]];//将父节点的砖块都加上，因为父节点在x下面  
        father[x] = px;
    }
    return father[x];
}
void _union(int a,int b)
{
    //将a放到b上
    int x = find(a);
    int y = find(b);
    if(x!=y)
    {
        father[x] = y;//父节点在下面 
        under[x] = sum[y];//x下面的砖块数就是y堆的个数
        sum[y] += sum[x];//y堆的个数要加上x堆的个数
    }
}
int main()
{
    init(N);
    int p;
    int a,b;
    char c;
    scanf("%d",&p);
    while(p--)
    {
        getchar();
        c = getchar();
        if(c=='M')
        {
            scanf("%d%d",&a,&b);
            _union(a,b);
        }else{
            scanf("%d",&a);
            find(a);
            printf("%d\n",under[a]);
        }
    }
    return 0;
}