Lowlink
(graph/lowlink.hpp)

• View this file on GitHub
• Last update: 2026-10-25 23:38:54+09:00
• Include: #include "graph/lowlink.hpp"

概要

• 無向グラフの橋・関節点・二重辺連結成分を求める。

使い方

• lowlink(n): $n$ 頂点 $0$ 辺の無向グラフを作る。
• add_edge(u, v): 辺 $(u, v)$ を追加し、辺番号を返す。辺番号は追加順。
• build(): 構築する。
• is_bridge(e): 辺 e が橋かを返す。
• is_articulation(v): 頂点 v が関節点かを返す。
• bridges(): 橋の辺番号を昇順に返す。
• articulation_points(): 関節点を昇順に返す。
• component(v): 頂点 v の属する二重辺連結成分の番号を返す。
• two_edge_connected_components(): 二重辺連結成分ごとの頂点のリストを返す。component(v) 番目のリストに v が入る。

制約

• $0 \le u, v < n$
• 多重辺・自己ループを含んでよい

計算量

• build: $\mathcal{O}(N + M)$
• bridges, articulation_points: $\mathcal{O}(N + M)$
• その他: $\mathcal{O}(1)$

Verified with

• test/aoj/GRL_3_A.test.cpp
• test/aoj/GRL_3_B.test.cpp
• test/library-checker/two_edge_connected_components.test.cpp
• test/unit/lowlink.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
struct lowlink {
public:
    lowlink() : lowlink(0) {
    }
    explicit lowlink(int n) : _n(n), g(n), ord(n, -1), low(n), comp(n, -1), art(n, false) {
    }
    int add_edge(int u, int v) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int e = int(edges.size());
        edges.emplace_back(u, v);
        g[u].emplace_back(v, e);
        g[v].emplace_back(u, e);
        return e;
    }
    void build() {
        int m = int(edges.size());
        bridge.assign(m, false);
        std::vector<int> it(_n, 0), par_edge(_n, -1), children(_n, 0);
        int t = 0;
        for (int r = 0; r < _n; r++) {
            if (ord[r] != -1) continue;
            std::vector<int> st = {r};
            ord[r] = low[r] = t++;
            while (!st.empty()) {
                int v = st.back();
                if (it[v] < int(g[v].size())) {
                    auto [u, e] = g[v][it[v]++];
                    if (e == par_edge[v]) continue;
                    if (ord[u] == -1) {
                        ord[u] = low[u] = t++;
                        par_edge[u] = e;
                        children[v]++;
                        st.push_back(u);
                    } else {
                        low[v] = std::min(low[v], ord[u]);
                    }
                } else {
                    st.pop_back();
                    if (st.empty()) continue;
                    int p = st.back();
                    low[p] = std::min(low[p], low[v]);
                    if (low[v] > ord[p]) bridge[par_edge[v]] = true;
                    if (low[v] >= ord[p] && p != r) art[p] = true;
                }
            }
            art[r] = children[r] >= 2;
        }
        _num_components = 0;
        for (int r = 0; r < _n; r++) {
            if (comp[r] != -1) continue;
            comp[r] = _num_components;
            std::vector<int> st = {r};
            while (!st.empty()) {
                int v = st.back();
                st.pop_back();
                for (auto [u, e] : g[v]) {
                    if (bridge[e] || comp[u] != -1) continue;
                    comp[u] = _num_components;
                    st.push_back(u);
                }
            }
            _num_components++;
        }
    }
    bool is_bridge(int e) const {
        assert(0 <= e && e < int(edges.size()));
        return bridge[e];
    }
    bool is_articulation(int v) const {
        assert(0 <= v && v < _n);
        return art[v];
    }
    std::vector<int> bridges() const {
        std::vector<int> res;
        for (int e = 0; e < int(edges.size()); e++) {
            if (bridge[e]) res.push_back(e);
        }
        return res;
    }
    std::vector<int> articulation_points() const {
        std::vector<int> res;
        for (int v = 0; v < _n; v++) {
            if (art[v]) res.push_back(v);
        }
        return res;
    }
    int component(int v) const {
        assert(0 <= v && v < _n);
        return comp[v];
    }
    std::vector<std::vector<int>> two_edge_connected_components() const {
        std::vector<std::vector<int>> res(_num_components);
        for (int v = 0; v < _n; v++) res[comp[v]].push_back(v);
        return res;
    }

private:
    int _n, _num_components = 0;
    std::vector<std::vector<std::pair<int, int>>> g;
    std::vector<std::pair<int, int>> edges;
    std::vector<int> ord, low, comp;
    std::vector<bool> art, bridge;
};

#line 2 "graph/lowlink.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
struct lowlink {
public:
    lowlink() : lowlink(0) {
    }
    explicit lowlink(int n) : _n(n), g(n), ord(n, -1), low(n), comp(n, -1), art(n, false) {
    }
    int add_edge(int u, int v) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int e = int(edges.size());
        edges.emplace_back(u, v);
        g[u].emplace_back(v, e);
        g[v].emplace_back(u, e);
        return e;
    }
    void build() {
        int m = int(edges.size());
        bridge.assign(m, false);
        std::vector<int> it(_n, 0), par_edge(_n, -1), children(_n, 0);
        int t = 0;
        for (int r = 0; r < _n; r++) {
            if (ord[r] != -1) continue;
            std::vector<int> st = {r};
            ord[r] = low[r] = t++;
            while (!st.empty()) {
                int v = st.back();
                if (it[v] < int(g[v].size())) {
                    auto [u, e] = g[v][it[v]++];
                    if (e == par_edge[v]) continue;
                    if (ord[u] == -1) {
                        ord[u] = low[u] = t++;
                        par_edge[u] = e;
                        children[v]++;
                        st.push_back(u);
                    } else {
                        low[v] = std::min(low[v], ord[u]);
                    }
                } else {
                    st.pop_back();
                    if (st.empty()) continue;
                    int p = st.back();
                    low[p] = std::min(low[p], low[v]);
                    if (low[v] > ord[p]) bridge[par_edge[v]] = true;
                    if (low[v] >= ord[p] && p != r) art[p] = true;
                }
            }
            art[r] = children[r] >= 2;
        }
        _num_components = 0;
        for (int r = 0; r < _n; r++) {
            if (comp[r] != -1) continue;
            comp[r] = _num_components;
            std::vector<int> st = {r};
            while (!st.empty()) {
                int v = st.back();
                st.pop_back();
                for (auto [u, e] : g[v]) {
                    if (bridge[e] || comp[u] != -1) continue;
                    comp[u] = _num_components;
                    st.push_back(u);
                }
            }
            _num_components++;
        }
    }
    bool is_bridge(int e) const {
        assert(0 <= e && e < int(edges.size()));
        return bridge[e];
    }
    bool is_articulation(int v) const {
        assert(0 <= v && v < _n);
        return art[v];
    }
    std::vector<int> bridges() const {
        std::vector<int> res;
        for (int e = 0; e < int(edges.size()); e++) {
            if (bridge[e]) res.push_back(e);
        }
        return res;
    }
    std::vector<int> articulation_points() const {
        std::vector<int> res;
        for (int v = 0; v < _n; v++) {
            if (art[v]) res.push_back(v);
        }
        return res;
    }
    int component(int v) const {
        assert(0 <= v && v < _n);
        return comp[v];
    }
    std::vector<std::vector<int>> two_edge_connected_components() const {
        std::vector<std::vector<int>> res(_num_components);
        for (int v = 0; v < _n; v++) res[comp[v]].push_back(v);
        return res;
    }

private:
    int _n, _num_components = 0;
    std::vector<std::vector<std::pair<int, int>>> g;
    std::vector<std::pair<int, int>> edges;
    std::vector<int> ord, low, comp;
    std::vector<bool> art, bridge;
};

Back to top page