带权并查集：银河英雄传说

· · 个人记录

　　带权并查集，大体思路与普通并查集相仿，只不过要

多维护更多的东西：例如权值等。

　　以这道题为例，要维护两个战舰之间的数量，我们可

以维护一个战舰到其根节点的距离ｄ，并查集首先要解

决“并“的问题，

inline void bing(int a,int b){
    int xx=find(a),yy=find(b);
    find(tail[yy]);
    d[xx]=d[tail[yy]]+1;
    fa[xx]=yy;
    tail[yy]=tail[xx];
}

　　taill数组代表了某个”头“所对应的“尾”；

我们先不要管find的操作，其作用就是发现x列所对应

的“头“，并且更新某个点的d。很显然，当前点的d就等于

要并到的那一列的”尾“+1；其余的就如同普通并查集了。

　　我们再来看find的操作：

  inline int find(int x){
    if (fa[x]==x) return x;
    else {
        find(fa[x]);
        d[x]=d[x]+d[fa[x]];
        return fa[x]=fa[fa[x]];
    }
}

　　这里有一个问题：为什么要先find，再更新d，最后

 更新fa数组呢？因为fa还是存的之前的，我们先更新完它所对应的

 d，然后显然的d[当前]要加上d[fa[当前点]]，最后更新fa，不然就

 没法顺水推舟般的更新当前点的d；
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
const int maxn=100006;
using namespace std;
int t;
int fa[maxn],d[maxn],tail[maxn];
inline int abs_(int x,int y){
    return x>y?x-y:y-x;
}
inline int find(int x){
    if (fa[x]==x) return x;
    else {
        find(fa[x]);
        d[x]=d[x]+d[fa[x]];
        return fa[x]=fa[fa[x]];
    }
}
inline void bing(int a,int b){
    int xx=find(a),yy=find(b);
    find(tail[yy]);
    d[xx]=d[tail[yy]]+1;
    fa[xx]=yy;
    tail[yy]=tail[xx];
}
int main(){
    for (int i=1;i<=30000;++i){
        fa[i]=tail[i]=i;
        d[i]=0;
    }
    cin>>t;
    for (int i=1,a,b;i<=t;++i){
        char q;
        cin>>q;
        scanf("%d%d",&a,&b);
//      cout<<q<<endl;
        if (q=='M'){
            bing(a,b);
        }
        else {
            if (fa[find(a)]!=fa[find(b)]) printf("-1\n");
            else {
                printf("%d\n",abs_(d[a],d[b])-1);
            }
        }
    }
    return 0;
}