[POJ1988 Cube Stacking]并差集

【题目大意】

同银河英雄传说。。。

【算法分析】

并差集之~

这题更简单，直接输出s[i]即可。

【其它】1A

。。。无意水，是在找银河英雄传说的提交网站时无意碰到的。。。

【CODE】

#include #include #include const int n=30000;
int T;
int f[31111],s[31111],tail[31111];
char c;

int gf(int x){
    if (f[x]==x) return x;
    int tf=gf(f[x]);
    s[x]+=s[f[x]];
    f[x]=tf;
    return tf;
}   

void Union(){
    int x,y;
    scanf("%d%d",&y,&x);
    gf(x); gf(y);
    s[f[y]]=1;
    int fy=f[y];
    f[f[y]]=tail[f[x]];
    tail[f[x]]=tail[fy];
}   

void Count(){
    int x;
    scanf("%d%d",&x);
    gf(x);
    printf("%dn",s[x]);
}   

int main(){
    for (int i=1;i<=n;i++){
        f[i]=i;
        s[i]=0;
        tail[i]=i;
    }   
    scanf("%d",&T);
    for (int i=1;i<=T;i++){
        c=getchar();
        while (c==’ ‘ || c==’n’) c=getchar();
        if (c==’M’) Union();
               else Count();
    }   
}