LowLink
(graph/lowlink.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

無向グラフの LowLink。 DFS 木の順序 ord と到達可能な最小順序 low を用いて、次を列挙する。

• 関節点 (articulation points)
• 橋 (bridges)

連結でないグラフにも対応する。

計算量

• build() : $O(V + E)$

使い方

1. LowLink g(n);
2. add_edge(u, v) で無向辺を追加
3. build() を呼ぶ
4. 結果を articulation, bridge などから参照

公開メンバ

• vector<int> ord : DFS 訪問順（未訪問は -1）
• vector<int> low : lowlink 値
• vector<int> par : DFS 木での親（根は -1）
• vector<int> articulation : 関節点の頂点番号一覧
• vector<pair<int, int>> bridge : 橋の一覧（(min(u,v), max(u,v)) 形式、昇順ソート済み）

補足

• 多重辺を考慮している。
• 自己ループは add_edge で無視する実装。
• is_bridge(i, j) は build() 後に使用する。

Verified with

• test/aoj_grl_3_b.test.cpp

Code

class LowLink {
    void dfs(int i, int p, int &pos){
        ord[i] = low[i] = pos++;
        int ch = 0, mul = 0;
        bool is_art = false;
        for (auto &&j : G[i]) {
            if(j == p && !mul){
                mul = 1;
                continue;
            }
            if(~ord[j]){
                low[i] = min(low[i], ord[j]);
                continue;
            }
            par[j] = i;
            ch++;
            dfs(j, i, pos);
            low[i] = min(low[i], low[j]);
            if(p != -1 && ord[i] <= low[j]) is_art = true;
            if(ord[i] < low[j]) bridge.emplace_back(min(i, j), max(i, j));
        }
        if(p == -1 && ch > 1) is_art = true;
        cut[i] = is_art;
    }
public:
    vector<int> ord, low, par, articulation;
    vector<pair<int, int>> bridge;
    vector<char> cut;
    vector<vector<int>> G;
    LowLink() = default;
    explicit LowLink(int n): ord(n, -1), low(n), par(n, -1), cut(n), G(n){}

    void add_edge(int u, int v){
        if(u != v){
            G[u].emplace_back(v);
            G[v].emplace_back(u);
        }
    }

    void build(){
        int n = G.size(), pos = 0;
        fill(ord.begin(), ord.end(), -1);
        fill(par.begin(), par.end(), -1);
        fill(cut.begin(), cut.end(), 0);
        articulation.clear();
        bridge.clear();
        for (int i = 0; i < n; ++i) {
            if(!~ord[i]) dfs(i, -1, pos);
        }
        for (int i = 0; i < n; ++i) {
            if(cut[i]) articulation.emplace_back(i);
        }
        sort(bridge.begin(), bridge.end());
    }

    inline bool is_bridge(int i, int j){
        if(ord[i] > ord[j]) swap(i, j);
        return ord[i] < low[j];
    }
};

/**
 * @brief LowLink
 */

#line 1 "graph/lowlink.cpp"
class LowLink {
    void dfs(int i, int p, int &pos){
        ord[i] = low[i] = pos++;
        int ch = 0, mul = 0;
        bool is_art = false;
        for (auto &&j : G[i]) {
            if(j == p && !mul){
                mul = 1;
                continue;
            }
            if(~ord[j]){
                low[i] = min(low[i], ord[j]);
                continue;
            }
            par[j] = i;
            ch++;
            dfs(j, i, pos);
            low[i] = min(low[i], low[j]);
            if(p != -1 && ord[i] <= low[j]) is_art = true;
            if(ord[i] < low[j]) bridge.emplace_back(min(i, j), max(i, j));
        }
        if(p == -1 && ch > 1) is_art = true;
        cut[i] = is_art;
    }
public:
    vector<int> ord, low, par, articulation;
    vector<pair<int, int>> bridge;
    vector<char> cut;
    vector<vector<int>> G;
    LowLink() = default;
    explicit LowLink(int n): ord(n, -1), low(n), par(n, -1), cut(n), G(n){}

    void add_edge(int u, int v){
        if(u != v){
            G[u].emplace_back(v);
            G[v].emplace_back(u);
        }
    }

    void build(){
        int n = G.size(), pos = 0;
        fill(ord.begin(), ord.end(), -1);
        fill(par.begin(), par.end(), -1);
        fill(cut.begin(), cut.end(), 0);
        articulation.clear();
        bridge.clear();
        for (int i = 0; i < n; ++i) {
            if(!~ord[i]) dfs(i, -1, pos);
        }
        for (int i = 0; i < n; ++i) {
            if(cut[i]) articulation.emplace_back(i);
        }
        sort(bridge.begin(), bridge.end());
    }

    inline bool is_bridge(int i, int j){
        if(ord[i] > ord[j]) swap(i, j);
        return ord[i] < low[j];
    }
};

/**
 * @brief LowLink
 */

Back to top page