POJ-1988 Cube Stacking

POJ-1988 Cube Stacking

#include <iostream>
#include <cstdio>
using namespace std;
#define MAX 30005
int n, x, y;
int fa[MAX], son[MAX], dis[MAX];
// fa父结点 son当前节点子树大小 dis当前节点到根结点距离
inline void init()
{
    for (int i = 1; i <= MAX; i++)
    {
        fa[i] = i;
        son[i] = 1;
    }
}

int Find(int t)
{
    if (fa[t] == t)
        return t;
    int tp = fa[t];
    fa[t] = Find(fa[t]);
    dis[t] += dis[tp]; //当前点到根结点的距离+=父结点到根结点的距离
    return fa[t];      //路径压缩
}

void join(int x, int y)
{
    int rx = Find(x);
    int ry = Find(y);
    if (rx != ry)
    {
        fa[ry] = rx;        // rx所在的子树放到ry所在子树之上
        dis[ry] = son[rx];  // ry到rx的距离就是rx所在子树的结点个数
        son[rx] += son[ry]; // rx所在子树结点个数要加上ry这一棵树子树
    }
}

int main ()
{
    scanf("%d", &n);
    init();
    char c;
    for (int i = 1; i <= n; i++)
    {
        getchar();
        scanf("%c", &c);
        if (c == 'M') //合并
        {
            scanf("%d%d", &x, &y);
            join(x, y);
        }
        else
        {
            scanf("%d", &x);
            printf("%d\n", son[Find(x)] - dis[x] - 1);
        }
    }
    return 0; 
}