LowLink
(cpp_src/graph/LowLink.hpp)

• View this file on GitHub
• Last update: 2023-12-31 13:48:59+09:00
• Include: #include "cpp_src/graph/LowLink.hpp"

橋

• DFS 木の辺 uv が橋 $\iff$ ord[$u$] < low_[$v$]

関節点

• DFS 木の根が関節点 $\iff$ (次数) > $1$
• DFS 木の根以外の頂点 $u$ が関節点 $\iff$ $u$ のある子 $v$ に対し ord[$u$] $\leq$ low[$v$]
• 特に、上記を満たす頂点の個数が、$u$ を取り除いたときの連結成分数

参考

• グラフ探索アルゴリズムとその応用

Verified with

• test/yosupo/two_edge_connected_components.test.cpp

Code

/**
 * @docs docs/LowLink.md
 */

// based on ei1333
// allow self loops, multiple edges
template <class T>
struct LowLink : Graph<T> {
   public:
    using Graph<T>::Graph;
    using Graph<T>::g;
    vector<int> ord, low, articulation;
    vector<Edge<T>> bridge;

    virtual void build() {
        used.assign(g.size(), 0);
        ord.assign(g.size(), 0);
        low.assign(g.size(), 0);
        int k = 0;
        for (int i = 0; i < g.size(); i++) {
            if (!used[i]) dfs(i, -1, k);
        }
    }

   private:
    vector<int> used;

    void dfs(int v, int par, int& k) {
        used[v] = true;
        low[v] = ord[v] = k++;
        bool is_articulation = false, seen = false;
        int cnt = 0;
        for (auto& e : g[v]) {
            if (e.to == par && !exchange(seen, true)) {
                continue;
            }
            if (!used[e.to]) {
                ++cnt;
                dfs(e.to, v, k);
                low[v] = min(low[v], low[e.to]);
                is_articulation |= (par >= 0 && low[e.to] >= ord[v]);
                if (ord[v] < low[e.to]) bridge.emplace_back(e);
            } else {
                low[v] = min(low[v], ord[e.to]);
            }
        }
        is_articulation |= (par == -1 && cnt > 1);
        if (is_articulation) articulation.push_back(v);
    }
};

#line 1 "cpp_src/graph/LowLink.hpp"
/**
 * @docs docs/LowLink.md
 */

// based on ei1333
// allow self loops, multiple edges
template <class T>
struct LowLink : Graph<T> {
   public:
    using Graph<T>::Graph;
    using Graph<T>::g;
    vector<int> ord, low, articulation;
    vector<Edge<T>> bridge;

    virtual void build() {
        used.assign(g.size(), 0);
        ord.assign(g.size(), 0);
        low.assign(g.size(), 0);
        int k = 0;
        for (int i = 0; i < g.size(); i++) {
            if (!used[i]) dfs(i, -1, k);
        }
    }

   private:
    vector<int> used;

    void dfs(int v, int par, int& k) {
        used[v] = true;
        low[v] = ord[v] = k++;
        bool is_articulation = false, seen = false;
        int cnt = 0;
        for (auto& e : g[v]) {
            if (e.to == par && !exchange(seen, true)) {
                continue;
            }
            if (!used[e.to]) {
                ++cnt;
                dfs(e.to, v, k);
                low[v] = min(low[v], low[e.to]);
                is_articulation |= (par >= 0 && low[e.to] >= ord[v]);
                if (ord[v] < low[e.to]) bridge.emplace_back(e);
            } else {
                low[v] = min(low[v], ord[e.to]);
            }
        }
        is_articulation |= (par == -1 && cnt > 1);
        if (is_articulation) articulation.push_back(v);
    }
};

Back to top page