[NOI2002 day1 银河英雄传说]并差集

【算法分析】

直接上一个并差集，然后+两个辅助数组s[i],tail[i]

s[i]表示f[i]到i的距离

tail[i]表示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,y;
    scanf("%d%d",&x,&y);
    if (gf(x)!=gf(y)){
        printf("-1n");
        return;
    }   
    int ans=abs(s[x]-s[y])-1;
    if (ans<0) ans=0;
    printf("%dn",ans);
}   

int main(){
    freopen("galaxy.in","r",stdin);
    freopen("galaxy.out","w",stdout);
    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();
    }   
}