并查集 POJ 1988

#include <cstdio>
#define N 30010
int pa[N]; //parent
int siz_tree[N]; //size of tree
int d[N]; //dist between node and root
int Find(int x)
{
    if(pa[x] == x) return x;
    int t = pa[x];
    pa[x] = Find(pa[x]);
    d[x] += d[t]; 
    return pa[x];
}
void Union(int x, int y)
{
    x = Find(x), y = Find(y);
    pa[x] = y;
    d[x] += siz_tree[y];
    siz_tree[y] += siz_tree[x];
    siz_tree[x] = 0;
}
int main()
{
    int p;
    while(~scanf("%d", &p))
    {
        for(int i = 0; i < N; i++) pa[i] = i, siz_tree[i] = 1, d[i] = 0;

        char c;
        int x, y;

        for(int i = 0; i < p; i++) {
            while(1) {
                c = getchar();
                if(c == 'M' || c == 'C') break;
            }
            if(c == 'M') {
                scanf("%d%d", &x, &y);
                Union(x, y);
            }
            else {
                scanf("%d", &x);
                Find(x);
                printf("%d
", d[x]);
            }
        }
    }
    return 0;
}