LowLinkを実装してみた。自分用の詰まった部分のメモも含む。

どういう問題をやるの

グラフが与えられて

関節点　その点を取ってしまうと、グラフの連結成分は増えてしまう(バラバラになる)
橋　その辺を取ってしまうと、グラフの連結成分は増えてしまう(バラバラになる)

これを求める。

Union-Findでつながってるかどうかを$ O(V + E) $で判定できるので、抜く頂点や辺を全通り試せば、$ O(V(V + E)), O(E(V + E)) $の計算量になる。

LowLinkという手法を使うことで、$ O(V + E) $にとどめることができる。

LowLinkのきもち

先行記事たち。ここら辺を見ながらこれをサブノートとして見る方がいい。

ei1333さん

アルゴリズムロジック

DFSしながら、ループを構成してるものに全部同じ番号を割り当てることで、ループ内なら基本的に点や辺抜いてもOKを実現させている(いくつかの例外あり)

low[]は、初めは今の頂点のDFS順番を入れる。そして、今の点からがすでに訪ねたことがある点に行きついたとき、その時点でループが完成されているので、訪ねたことある頂点のDFS順を入れる。

そして、今のDFSの再帰を終わらせて戻りながら、その今の再帰を呼び出したものにも衝突した点でのlow[]を、minで伝播させる。

橋の判定は

親のDFS順 < 子のlow
- 子のlowはループ作ってるなら、ループ内でみんな同じだが、みんな親より後にDFSで見たので、これが必ず成り立つ。

関節点の判定は

根ノードなら、子が2つ以上
- 1つしかないなら明らかに取り除いても、全体のグラフを複数の連結成分に分割させない。
根ノード以外だと、親のDFS順 <= 子のlow[]
- 橋と違って、子のlowが親と等しい=ひとつのループを構成する時でも、そこを取り除いたらループ自体は壊れることから、イコールの条件を追加。

実際の例

~~ここが一番の本体だったりする。~~どこにも無かった一歩ずつの例の動画とかを載せてみた。将来の私も含めて困ったら見にこよう。

実装例

/**
 * 関節点と橋をO(E + V)で求めるアルゴリズム.
 */
class LowLink {
    typedef std::vector<std::vector<int>> Edge;

    /**
    * 訪問したことがある頂点かどうか.
    */
    vector<bool> visited;
    /**
    * 順序.
    */
    vector<int> order;
    /**
    * 配列low. low[親] < low[子]なら、ブリッジとなる。
    */
    vector<int> low;

public:
    /**
    * 与えられる木。隣接リスト形式でコストは含まれない.親は-1とする。
    */
    Edge E;
    /**
    * 関節点　その点を取り除くと全体が不連結になる点.
    */
    vector<int> articulation_points;
    /**
    * 橋。pair<int, int>でfirst < secondで橋となる両端を入れる.
    */
    vector<pair<int, int>> bridge;

private:

    void dfs(int now, int parent, int& count) {
        visited[now] = true;
        order[now] = count;
        low[now] = order[now];
        count++;
        bool is_art = false;/* 関節点であるかどうか */
        int son_count = 0;
        for (auto next : E[now]) {
            if (!visited[next]) {
                son_count++;
                dfs(next, now, count);
                if (next != parent)
                    low[now] = min(low[now], low[next]); // ループに行きついたときに、戻る際の伝播
                //関節点か イコールがつくのは、ひとまとまりのグループ内のlow[]は関節点のlow[]と同じ値だから。端はもうこれ以上伸びないので、関節点にカウントしない
                if (parent != -1 && order[now] <= low[next])
                    is_art = true;
                //橋か
                if (order[now] < low[next])
                    bridge.push_back(make_pair(min(now, next), max(now, next)));
            }
            else {
                //すでに行ったことある頂点=後退辺
                if (next != parent)
                    low[now] = min(low[now], order[next]);// ループに行きついた時にorder[]を代入
            }

        }
        //根は2つ以上の子があるなら、関節点
        if (parent == -1 && son_count >= 2)
            is_art = true;
        if (is_art)
            articulation_points.push_back(now);
    }

public:
    /**
    * 渡すのは隣接リスト形式のグラフ。辺の長さは受け付けない.
    *
    * \param e
    */
    LowLink(const Edge& e) {
        E = e;
        visited.assign(E.size(), 0);
        order.assign(E.size(), 0);
        low.assign(E.size(), 0);
    }
    /**
    * 計算の際に呼び出す。各連結成分ごとにDFSしている。.
    *
    */
    void build() {
        int count = 0;
        for (int i = 0; i < E.size(); i++) {
            if (!visited[i])
                dfs(i, -1, count);
        }
    }
};