競プロのライブラリ整理~最小全域木~

長らく逃げ続けていた最小全域木のライブラリの作成でしたが、昨日解いたShichikuji and Power Gridにおいて必要であったので作成しました。今のところは実装の容易なクラスカル法しかありませんが、気が向いたらプリム法のライブラリも作成したいと思います。

また、クラスカル法を書くにあたり、コードはこちらの記事のものを参考にさせていただいたのと、この記事ではクラスカル法の中身については触れないので他の記事を読んでください。

クラスカル法とは？

重み付き連結グラフの最小全域木を求めるアルゴリズム

全域木…グラフが連結のまま辺を消去して得られる木のこと
最小全域木…辺の重さの総和が最小となる全域木のこと

計算量

頂点数$n$,辺数$m$のときの計算量は

辺のコストの昇順でのソートで$O(m \log{n})$、UnionFind木へのuniteで$O(m \alpha{(n)})$なので、$O(m \log{n})$となります。

自分のコードの説明

以下のコードはUnionFindのライブラリのせいで長く見えますが、重要なのはKruskalという関数のみです。

この関数内で必要な辺を順に追加しており、最終的に最小全域木のコストを返り値として返します。もちろん、最小全域木に含まれる辺のみを抜き出すことも可能です。

問題例

①ABC065-D Built?

基本問題です。

②Codeforces Round #597(Div.2) Shichikuji and Power Grid

超頂点を導入することでスムーズに解くことができます。
この記事に解法を書きました。

コード

Kruslal.cc

//以下、素集合と木は同じものを表す
class UnionFind{
public:
    vector<ll> parent; //parent[i]はiの親
    vector<ll> siz; //素集合のサイズを表す配列(1で初期化)
    map<ll,vector<ll>> group; //集合ごとに管理する(key:集合の代表元、value:集合の要素の配列)
    ll n; //要素数

    //コンストラクタ
    UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){ 
        //全ての要素の根が自身であるとして初期化
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //データxの属する木の根を取得(経路圧縮も行う)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//代入式の値は代入した変数の値なので、経路圧縮できる
    }

    //xとyの木を併合
    void unite(ll x,ll y){
        ll rx=root(x);//xの根
        ll ry=root(y);//yの根
        if(rx==ry) return;//同じ木にある時
        //小さい集合を大きい集合へと併合(ry→rxへ併合)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx;//xとyが同じ木にない時はyの根ryをxの根rxにつける
    }

    //xとyが属する木が同じかを判定
    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    //xの素集合のサイズを取得
    ll size(ll x){
        return siz[root(x)];
    }

    //素集合をそれぞれグループ化
    void grouping(){
        //経路圧縮を先に行う
        REP(i,n)root(i);
        //mapで管理する(デフォルト構築を利用)
        REP(i,n)group[parent[i]].PB(i);
    }

    //素集合系を削除して初期化
    void clear(){
        REP(i,n){parent[i]=i;}
        siz=vector<ll>(n,1);
        group.clear();
    }
};

//辺の構造体
struct Edge{
    ll u,v,cost;
    //後ろにconstつける！
    bool operator<(const Edge& e) const {return this->cost<e.cost;}
};

//クラスカル法
//ret:=最小全域木の重みの総和
//n:=頂点の総数
//計算量:=O(m log{n})
ll Kruskal(vector<Edge> &edges,ll n){
    sort(ALL(edges));//辺の重みの昇順
    UnionFind uf(n);
    ll ret=0;
    FORA(e,edges){
        //その辺を加える必要があるか
        if (!uf.same(e.u,e.v)){
            uf.unite(e.u,e.v);
            ret+=e.cost;
        }
    }
    return ret;
}