Low Link - 関節点と橋
(Library/Graph/LowLink.hpp)

View this file on GitHub
Last update: 2026-02-13 15:23:31+09:00
Include: #include "Library/Graph/LowLink.hpp"

Low Link - 関節点と橋

頂点数 $V$ 辺数 $E$ の無向グラフの関節点と橋を検出します。

関節点: その頂点を取り除くとグラフの連結成分数が増加する頂点
橋: その辺を取り除くとグラフの連結成分数が増加する辺

Function

Constructor

LowLink(Graph<CostType> &graph)

グラフ $G$ を頂点数 $V$ 辺数 $E$ の graph で初期化し、関節点と橋を事前計算します。

制約

$G$ は無向グラフ

計算量

$\textrm{O}(V + E)$

ArticulationPoint

vector<Vertex> &ArticulationPoint()

グラフに含まれるすべての関節点のリストを返します。

計算量

$\textrm{O}(1)$

Bridge

vector<pair<Vertex, Vertex>> &Bridge()

グラフに含まれるすべての橋のリストを返します。
各橋は頂点ペア $(u, v)$ として表現され、$u < v$ となるように正規化されています。

計算量

$\textrm{O}(1)$

EulerTour

pair<int, int> EulerTour(const Vertex v) const

DFS における頂点 $v$ の入時刻と出時刻を返します。

計算量

$\textrm{O}(1)$

Depends on

Verified with

Code

#pragma once

#include "Graph.hpp"

template<typename WeightType>
class LowLink{
    public:
    LowLink(Graph<WeightType> &graph) : G(graph), V(graph.VertexSize()), ord_(V, -1), low_(V, -1), in_(V), out_(V){
        for(int i = 0, k = 0, t = 0; i < V; ++i){
            if(ord_[i] == -1){
                k = dfs(i, -1, k, t);
            }
        }
    }

    vector<Vertex> &ArticulationPoint(){
        return articulation_point_;
    }

    vector<pair<Vertex, Vertex>> &Bridge(){
        return bridge_;
    }

    pair<int, int> EulerTour(const Vertex v) const {
        return {in_[v], out_[v]};
    }

    private:
    Graph<WeightType> &G;
    int V;
    vector<int> ord_, low_, in_, out_;
    vector<Vertex> articulation_point_;
    vector<pair<Vertex, Vertex>> bridge_;

    int dfs(Vertex v, int p, int k, int &t){
        in_[v] = t++;
        low_[v] = (ord_[v] = k++);
        int cnt = 0;
        bool is_articulation = false, second = false;
        for(int u : G[v]){
            if(ord_[u] == -1){
                ++cnt;
                k = dfs(u, v, k, t);
                low_[v] = min(low_[v], low_[u]);
                is_articulation |= (p != -1) && (low_[u] >= ord_[v]);
                if(ord_[v] < low_[u]){
                    bridge_.emplace_back(minmax(u, v));
                }
            }
            else if(u != p || second){
                low_[v] = min(low_[v], ord_[u]);
            }
            else{
                second = true;
            }
        }
        is_articulation |= (p == -1) && (cnt > 1);
        if(is_articulation) articulation_point_.emplace_back(v);
        out_[v] = t;
        return k;
    }
};

#line 2 "Library/Graph/LowLink.hpp"

#line 2 "Library/Graph/Graph.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/Graph/Graph.hpp"

using Vertex = int;

template<typename WeightType = int32_t>
struct Edge{
    public:
    Edge() = default;

    Edge(Vertex from_, Vertex to_, WeightType weight_ = 1, int idx_ = -1) :
        from(from_), to(to_), cost(weight_), idx(idx_){}
    
    bool operator<(const Edge<WeightType> &e) const {return cost < e.cost;}

    operator int() const {return to;}

    Vertex from, to;
    WeightType cost;
    int idx;
};

template<typename WeightType = int32_t>
class Graph{
    public:
    Graph() = default;

    Graph(int V) : edge_size_(0), adjacent_list_(V){}
    
    inline void AddUndirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
        adjacent_list_[v].push_back(Edge<WeightType>(v, u, w, idx));
    }
    
    inline void AddDirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
    }

    inline size_t VertexSize() const {
        return adjacent_list_.size();
    }

    inline size_t EdgeSize() const {
        return edge_size_;
    }

    inline vector<Edge<WeightType>> &operator[](const Vertex v){
        return adjacent_list_[v];
    }

    inline const vector<Edge<WeightType>> &operator[](const Vertex v) const {
        return adjacent_list_[v];
    }
    
    private:
    size_t edge_size_;
    vector<vector<Edge<WeightType>>> adjacent_list_;
};

template<typename WeightType = int32_t>
Graph<WeightType> InputGraph(int N, int M, int padding = -1, bool weighted = false, bool directed = false){
    Graph<WeightType> G(N);
    for(int i = 0; i < M; ++i){
        Vertex u, v; WeightType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        if(directed) G.AddDirectedEdge(u, v, w);
        else G.AddUndirectedEdge(u, v, w);
    }
    return G;
}
#line 4 "Library/Graph/LowLink.hpp"

template<typename WeightType>
class LowLink{
    public:
    LowLink(Graph<WeightType> &graph) : G(graph), V(graph.VertexSize()), ord_(V, -1), low_(V, -1), in_(V), out_(V){
        for(int i = 0, k = 0, t = 0; i < V; ++i){
            if(ord_[i] == -1){
                k = dfs(i, -1, k, t);
            }
        }
    }

    vector<Vertex> &ArticulationPoint(){
        return articulation_point_;
    }

    vector<pair<Vertex, Vertex>> &Bridge(){
        return bridge_;
    }

    pair<int, int> EulerTour(const Vertex v) const {
        return {in_[v], out_[v]};
    }

    private:
    Graph<WeightType> &G;
    int V;
    vector<int> ord_, low_, in_, out_;
    vector<Vertex> articulation_point_;
    vector<pair<Vertex, Vertex>> bridge_;

    int dfs(Vertex v, int p, int k, int &t){
        in_[v] = t++;
        low_[v] = (ord_[v] = k++);
        int cnt = 0;
        bool is_articulation = false, second = false;
        for(int u : G[v]){
            if(ord_[u] == -1){
                ++cnt;
                k = dfs(u, v, k, t);
                low_[v] = min(low_[v], low_[u]);
                is_articulation |= (p != -1) && (low_[u] >= ord_[v]);
                if(ord_[v] < low_[u]){
                    bridge_.emplace_back(minmax(u, v));
                }
            }
            else if(u != p || second){
                low_[v] = min(low_[v], ord_[u]);
            }
            else{
                second = true;
            }
        }
        is_articulation |= (p == -1) && (cnt > 1);
        if(is_articulation) articulation_point_.emplace_back(v);
        out_[v] = t;
        return k;
    }
};

Low Link - 関節点と橋 (Library/Graph/LowLink.hpp)

Low Link - 関節点と橋

Function

Constructor

ArticulationPoint

Bridge

EulerTour

Depends on

Verified with

Code

Low Link - 関節点と橋
(Library/Graph/LowLink.hpp)