LowLink
(graph/lowlink.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/lowlink.hpp"

Overview

LowLink is a DFS technique for undirected graphs. It records, for each vertex, the earliest DFS-order vertex reachable by going down zero or more tree edges and then using at most one back edge.

This information identifies:

articulation points: vertices whose removal increases the number of connected components;
bridges: edges whose removal increases the number of connected components.

Use it for network vulnerability problems, bridge counting, biconnected component preprocessing, and similar undirected connectivity tasks.

Graph Orientation

Undirected only. Build the graph with add_edge. LowLink is not the right tool for directed bridges or directed articulation-like notions.

How to Use It

Build the graph with add_edge, not two calls to add_directed_edge. The shared edge id is what lets the DFS skip exactly the tree edge it came from, while still handling parallel edges correctly.

The result contains these members:

Member	Type / Signature	Meaning
`ord`	`std::vector<int>`	`ord[v]` is the DFS visit order of `v`.
`low`	`std::vector<int>`	`low[v]` is the minimum `ord` reachable from `v`’s DFS subtree using at most one back edge.
`articulation`	`std::vector<int>`	Sorted list of articulation point vertices.
`bridges`	`std::vector<Edge<T>>`	Bridge edges as `Edge<T>` values.
`bridge_ids`	`std::vector<int>`	Sorted list of bridge edge ids.

For a DFS tree edge v -> to, it is a bridge when ord[v] < low[to]. A non-root vertex v is an articulation point when some child to has ord[v] <= low[to]. A DFS root is an articulation point when it has at least two DFS children.

Functions

Function	Signature	Description	Complexity
`lowlink`	`template <class T> LowLinkResult<T> lowlink(const Graph<T>& g)`	Computes `ord`, `low`, `articulation`, `bridges`, and `bridge_ids`.	$O(N + M)$

Example

#include "graph/graph.hpp"
#include "graph/lowlink.hpp"
#include <iostream>

int main() {
    m1une::graph::Graph<> g(4);
    g.add_edge(0, 1);
    g.add_edge(1, 2);
    int bridge = g.add_edge(1, 3);
    g.add_edge(2, 0);

    auto res = m1une::graph::lowlink(g);
    std::cout << res.articulation[0] << "\n";  // 1
    std::cout << (res.bridge_ids[0] == bridge) << "\n";  // 1
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_LOWLINK_HPP
#define M1UNE_GRAPH_LOWLINK_HPP 1

#include <algorithm>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

template <class T>
struct LowLinkResult {
    std::vector<int> ord;
    std::vector<int> low;
    std::vector<int> articulation;
    std::vector<Edge<T>> bridges;
    std::vector<int> bridge_ids;
};

template <class T>
LowLinkResult<T> lowlink(const Graph<T>& g) {
    int n = g.size();
    LowLinkResult<T> result;
    result.ord.assign(n, -1);
    result.low.assign(n, -1);
    int now = 0;

    auto dfs = [&](auto self, int v, int parent_edge) -> void {
        result.ord[v] = result.low[v] = now++;
        int child_count = 0;
        bool is_articulation = false;

        for (const auto& e : g[v]) {
            if (!e.alive) continue;
            if (e.id == parent_edge) continue;
            int to = e.to;
            if (result.ord[to] == -1) {
                child_count++;
                self(self, to, e.id);
                result.low[v] = std::min(result.low[v], result.low[to]);
                if (parent_edge != -1 && result.ord[v] <= result.low[to]) is_articulation = true;
                if (result.ord[v] < result.low[to]) {
                    result.bridges.push_back(e);
                    result.bridge_ids.push_back(e.id);
                }
            } else {
                result.low[v] = std::min(result.low[v], result.ord[to]);
            }
        }

        if (parent_edge == -1 && child_count >= 2) is_articulation = true;
        if (is_articulation) result.articulation.push_back(v);
    };

    for (int v = 0; v < n; v++) {
        if (result.ord[v] == -1) dfs(dfs, v, -1);
    }
    std::sort(result.articulation.begin(), result.articulation.end());
    std::sort(result.bridge_ids.begin(), result.bridge_ids.end());
    return result;
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_LOWLINK_HPP

#line 1 "graph/lowlink.hpp"



#include <algorithm>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#include <cassert>
#include <utility>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 8 "graph/lowlink.hpp"

namespace m1une {
namespace graph {

template <class T>
struct LowLinkResult {
    std::vector<int> ord;
    std::vector<int> low;
    std::vector<int> articulation;
    std::vector<Edge<T>> bridges;
    std::vector<int> bridge_ids;
};

template <class T>
LowLinkResult<T> lowlink(const Graph<T>& g) {
    int n = g.size();
    LowLinkResult<T> result;
    result.ord.assign(n, -1);
    result.low.assign(n, -1);
    int now = 0;

    auto dfs = [&](auto self, int v, int parent_edge) -> void {
        result.ord[v] = result.low[v] = now++;
        int child_count = 0;
        bool is_articulation = false;

        for (const auto& e : g[v]) {
            if (!e.alive) continue;
            if (e.id == parent_edge) continue;
            int to = e.to;
            if (result.ord[to] == -1) {
                child_count++;
                self(self, to, e.id);
                result.low[v] = std::min(result.low[v], result.low[to]);
                if (parent_edge != -1 && result.ord[v] <= result.low[to]) is_articulation = true;
                if (result.ord[v] < result.low[to]) {
                    result.bridges.push_back(e);
                    result.bridge_ids.push_back(e.id);
                }
            } else {
                result.low[v] = std::min(result.low[v], result.ord[to]);
            }
        }

        if (parent_edge == -1 && child_count >= 2) is_articulation = true;
        if (is_articulation) result.articulation.push_back(v);
    };

    for (int v = 0; v < n; v++) {
        if (result.ord[v] == -1) dfs(dfs, v, -1);
    }
    std::sort(result.articulation.begin(), result.articulation.end());
    std::sort(result.bridge_ids.begin(), result.bridge_ids.end());
    return result;
}

}  // namespace graph
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

LowLink
(graph/lowlink.hpp)

Overview

Graph Orientation

How to Use It

Functions

Example

Depends on

Required by

Verified with

Code

LowLink (graph/lowlink.hpp)

Overview

Graph Orientation

How to Use It

Functions

Example

Depends on

Required by

Verified with

Code

LowLink
(graph/lowlink.hpp)