1988:Cube Stacking

keyword

union-find　C

概要

1~N(=30000)の番号が付いた立方体がある。このとき、P(<10^5)個のクエリに答える問題。クエリの1つは、Xを含む山をYを含む山の上に積む。もう一つのクエリは、Xの下にいくつ立方体があるか出力する。
集合のマージがメインなのでunion-findを使う。集合の個数と、ルートまでの長さを覚えておけばよい。詳細はソース参照。ちなみに自分の場合union-findではランクを使わず経路圧縮しかしないので計算量がどこかで増えている可能性がある。

int pars[30002];
int counts[30002];
int lens[30002];

int getRoot(int x){ 
    int xx, y;
    if(x == pars[x])
        return x;
    xx = getRoot(pars[x]);
    lens[x] = lens[x] + lens[pars[x]];
    return pars[x] = xx;
}

void move(int x, int y){
    int xx = getRoot(x), yy = getRoot(y);
    pars[yy] = xx;
    lens[yy] = counts[xx];
    counts[xx] += counts[yy];
}

int count(int x){
    int xx = getRoot(x);
    return counts[xx] - lens[x] - 1;
}

main(){
    int i, x, y, P;
    char c;
    for(i=0;i<=30000;i++)
        pars[i] = i;
    for(i=0;i<=30000;i++)
        lens[i] = 0;
    for(i=0;i<=30000;i++)
        counts[i] = 1;
    scanf("%d\n",&P);
    for(i=0;i<P;i++){
        scanf("%c",&c);
        if(c=='M'){
            scanf("%d%d\n",&x,&y);
            move(x,y);
        }
        else{
            scanf("%d\n",&x);
            printf("%d\n", count(x));
        }
    }
}