Lowlink (橋・関節点)
(Src/Graph/Components/Lowlink.hpp)

View this file on GitHub
Last update: 2025-06-09 10:00:52+09:00
Include: #include "Src/Graph/Components/Lowlink.hpp"

概要

与えられた無向グラフに対して各頂点が関節点か、各辺が橋かを判定します。

ライブラリの使い方

コンストラクタ

(1) Lowlink()
(2) Lowkink(u32 n)

(1) 使用を想定していない (2) 頂点集合を $\{ 0, 1, 2, \dots, n - 1 \}$ で初期化する。

addEdge

u32 addEdge(u32 u, u32 v)

辺 $\{ u, v \}$ を追加する。この辺が何番目(0-indexed)に追加された辺かを返す。

size

constexpr usize size() const noexcept

頂点集合のサイズを返す。

edgeSize

constexpr usize edgeSize() const noexcept

現在の辺集合のサイズを返す。

operator[]

const std::vector<std::pair<u32, u32>>& operator[](u32 v) cnost noexcept

現在のグラフの頂点 $v$ と接続している辺のリストを返す。

firstが隣接している頂点
secondがその辺が何番目にaddEdgeによって追加されたかの番号(0-indexed)

edge

const std::pair<u32, u32>& edge(u32 i) const noexcept

$i$ 番目(0-indexed)にaddEdgeによって追加された辺を返す。

以降のメンバはbuild()を呼んだ後に呼ばれることが想定されている。

build

LowlinkResponse build() const

現在のグラフで橋・関節点を列挙する。

計算量: $O(

LowlinkResponse

isArticulation

inline bool isArticulation(u32 v) const 

頂点 $v$ が関節点かどうかを判定する。

isBridge

inline bool isBridge(u32 i) const

$i$ 番目の辺が橋かどうか判定する。

cut

inline u32 cut(u32 v) const

頂点 $v$ と $v$ を端点に持つ辺を削除したとき、グラフが何個の連結成分に分かれるかを返す。

参考

T.コメルン, C.ライザーソン, R.リベスト, C.シュタイン, アルゴリズムイントロダクション第３版第2巻第22章

Depends on

標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

Code

#pragma once

#include "../../Template/TypeAlias.hpp"

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

class Lowlink {
public:

    using V = usize;

    using ID = usize;

private:

    class LowlinkResponse {
    public:

        LowlinkResponse() = default;

        LowlinkResponse(std::vector<u32>&& articulation, std::vector<bool>&& bridge)
            : articulation_{std::move(articulation)}, bridge_{std::move(bridge)} {}

        inline bool isArticulation(V v) const {
            assert(v < articulation_.size());
            return articulation_[v] > 1u;
        }

        inline u32 cut(V v) const {
            assert(v < articulation_.size());
            return articulation_[v];
        }

        inline bool isBridge(ID i) const {
            assert(i < bridge_.size());
            return bridge_[i];
        }

    private:

        std::vector<u32> articulation_;

        std::vector<bool> bridge_;

    };

    static constexpr usize INVALID{static_cast<usize>(-1)};

    usize n_{}, m_{};

    std::vector<std::vector<std::pair<V, ID>>> g_;

    std::vector<std::pair<V, V>> e_;

    void dfs(V v, V p, u32& t, std::vector<u32>& articulation, 
            std::vector<bool>& bridge, std::vector<usize>& in, std::vector<usize>& low) const {
        low[v] = in[v] = t++;
        u32 deg{}; 
        for (const auto& [x, i] : g_[v]) {
            if (in[x] == INVALID) {
                deg++;
                dfs(x, v, t, articulation, bridge, in, low);
                low[v] = std::min(low[v], low[x]);
                if (p != INVALID and low[x] >= in[v]) {
                    articulation[v]++;
                }
                if (low[x] > in[v]) {
                    bridge[i] = true;
                }
            }
            else if (x != p) {
                low[v] = std::min(low[v], in[x]);
            }
        }
        if (p == INVALID) {
            articulation[v] = deg;
        }
    }

public:

    constexpr usize size() const noexcept {
        return n_;
    }

    constexpr usize edgeSize() const noexcept {
        return m_;
    }

    Lowlink() = default;

    explicit Lowlink(usize n) 
        : n_{n}, m_{}, g_(n) {
        g_.shrink_to_fit();
    }
    
    ID addEdge(V u, V v) {
        ID res{m_++};
        e_.emplace_back(u, v);
        g_[u].emplace_back(v, res);
        g_[v].emplace_back(u, res);
        return res;
    }

    const std::vector<std::pair<V, ID>>& operator[](V v) const noexcept {
        assert(v < size());
        return g_[v];
    }
    const std::pair<V, V>& edge(ID i) const noexcept {
        assert(i < edgeSize());
        return e_[i];
    }

    LowlinkResponse build() const {
        u32 t{};
        std::vector<u32> articulation(size(), 1u);
        std::vector<usize> in(size(), INVALID), low(size());
        std::vector<bool> bridge(edgeSize());
        for (u32 v{} ; v < size() ; v++) if (in[v] == INVALID) {
            dfs(v, INVALID, t, articulation, bridge, in, low);
        }
        return LowlinkResponse{ std::move(articulation), std::move(bridge) };
    }

};

} // namespace zawa

#line 2 "Src/Graph/Components/Lowlink.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Graph/Components/Lowlink.hpp"

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

class Lowlink {
public:

    using V = usize;

    using ID = usize;

private:

    class LowlinkResponse {
    public:

        LowlinkResponse() = default;

        LowlinkResponse(std::vector<u32>&& articulation, std::vector<bool>&& bridge)
            : articulation_{std::move(articulation)}, bridge_{std::move(bridge)} {}

        inline bool isArticulation(V v) const {
            assert(v < articulation_.size());
            return articulation_[v] > 1u;
        }

        inline u32 cut(V v) const {
            assert(v < articulation_.size());
            return articulation_[v];
        }

        inline bool isBridge(ID i) const {
            assert(i < bridge_.size());
            return bridge_[i];
        }

    private:

        std::vector<u32> articulation_;

        std::vector<bool> bridge_;

    };

    static constexpr usize INVALID{static_cast<usize>(-1)};

    usize n_{}, m_{};

    std::vector<std::vector<std::pair<V, ID>>> g_;

    std::vector<std::pair<V, V>> e_;

    void dfs(V v, V p, u32& t, std::vector<u32>& articulation, 
            std::vector<bool>& bridge, std::vector<usize>& in, std::vector<usize>& low) const {
        low[v] = in[v] = t++;
        u32 deg{}; 
        for (const auto& [x, i] : g_[v]) {
            if (in[x] == INVALID) {
                deg++;
                dfs(x, v, t, articulation, bridge, in, low);
                low[v] = std::min(low[v], low[x]);
                if (p != INVALID and low[x] >= in[v]) {
                    articulation[v]++;
                }
                if (low[x] > in[v]) {
                    bridge[i] = true;
                }
            }
            else if (x != p) {
                low[v] = std::min(low[v], in[x]);
            }
        }
        if (p == INVALID) {
            articulation[v] = deg;
        }
    }

public:

    constexpr usize size() const noexcept {
        return n_;
    }

    constexpr usize edgeSize() const noexcept {
        return m_;
    }

    Lowlink() = default;

    explicit Lowlink(usize n) 
        : n_{n}, m_{}, g_(n) {
        g_.shrink_to_fit();
    }
    
    ID addEdge(V u, V v) {
        ID res{m_++};
        e_.emplace_back(u, v);
        g_[u].emplace_back(v, res);
        g_[v].emplace_back(u, res);
        return res;
    }

    const std::vector<std::pair<V, ID>>& operator[](V v) const noexcept {
        assert(v < size());
        return g_[v];
    }
    const std::pair<V, V>& edge(ID i) const noexcept {
        assert(i < edgeSize());
        return e_[i];
    }

    LowlinkResponse build() const {
        u32 t{};
        std::vector<u32> articulation(size(), 1u);
        std::vector<usize> in(size(), INVALID), low(size());
        std::vector<bool> bridge(edgeSize());
        for (u32 v{} ; v < size() ; v++) if (in[v] == INVALID) {
            dfs(v, INVALID, t, articulation, bridge, in, low);
        }
        return LowlinkResponse{ std::move(articulation), std::move(bridge) };
    }

};

} // namespace zawa

Lowlink (橋・関節点) (Src/Graph/Components/Lowlink.hpp)

概要