Bridge tree (+ 二重辺連結成分分解)
(Src/Graph/Components/BridgeTree.hpp)

• View this file on GitHub
• Last update: 2025-06-12 16:53:31+09:00
• Include: #include "Src/Graph/Components/BridgeTree.hpp"

概要

二辺連結成分をまとめて一頂点にし、グラフを縮約します。このグラフは木であり、各辺は元のグラフでは橋です。

ライブラリ

constructor

BridgeTree() = default;
explicit BridgeTree(const std::vector<std::vector<T>>& g)

無向グラフの隣接リストを与える。Tはstd::integral<T>がtrueである必要がある。

size

inline usize size() const noexcept

縮約後の頂点数を返す

operator[]

const std::vector<V>& operator[](V v) const;

縮約後の頂点 $v$ の隣接する頂点の列を返す。ここで、V = usizeである。

component

const std::vector<T>& component(V v) const

縮約後の頂点 $v$ に対応している元のグラフの頂点の列を返す。

components

const std::vector<std::vector<T>>& components() const

componentの列である。すなわち二重辺連結成分分解した列を返す。

メモ

内部でunordered_mapを使って多重辺を処理しているので、ちょっとオーバヘッドがやばそう？

LCでは133msで普通に良さそうだったけど。

Depends on

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

Verified with

• Test/LC/two_edge_connected_components.test.cpp

Code

#pragma once

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

#include <concepts>
#include <vector>
#include <unordered_map>

namespace zawa {

template <std::integral T>
class BridgeTree {
public:

    using V = usize;

    BridgeTree() = default;

    explicit BridgeTree(const std::vector<std::vector<T>>& g) : m_id(g.size()) {
        const usize n = g.size();
        std::vector<usize> low(n), ord(n);
        std::vector<T> vs;
        std::vector<std::pair<T, T>> bridge;
        usize time = 1, id = 0;
        auto dfs = [&](auto dfs, T v, T p) -> void {
            low[v] = ord[v] = time++;
            std::unordered_map<T, usize> cnt;
            for (T x : g[v]) cnt[x]++;
            for (auto [x, c] : cnt) if (x != p) {
                if (ord[x]) {
                    low[v] = std::min(low[v], ord[x]);
                }
                else {
                    dfs(dfs, x, v);
                    low[v] = std::min(low[v], low[x]);
                    if (c == 1u and ord[v] < low[x]) {
                        std::vector<T> cur; 
                        while (vs.size() and low[x] <= low[vs.back()]) {
                            cur.push_back(vs.back());
                            m_id[vs.back()] = m_comp.size();
                            vs.pop_back();
                        }
                        bridge.emplace_back(x, v);
                        m_comp.push_back(std::move(cur));
                    }
                }
            }
            vs.push_back(v);
        };
        for (usize v = 0 ; v < n ; v++) if (!ord[v]) {
            dfs(dfs, v, static_cast<T>(-1));
            if (vs.size()) {
                std::vector<T> cur;
                while (vs.size()) {
                    m_id[vs.back()] = m_comp.size();
                    cur.push_back(vs.back());
                    vs.pop_back();
                }
                m_comp.push_back(std::move(cur));
            }
        }
        m_g.resize(m_comp.size());
        for (auto [u, v] : bridge) {
            const V p = m_id[u], q = m_id[v];
            m_g[p].push_back(q);
            m_g[q].push_back(p);
        }
    }

    inline usize size() const noexcept {
        return m_g.size();
    }

    const std::vector<V>& operator[](V v) const {
        assert(v < size());
        return m_g[v];
    }

    const std::vector<std::vector<T>>& components() const {
        return m_comp;
    }

    const std::vector<T>& component(V v) const {
        assert(v < size());
        return m_comp[v];
    }

private:

    std::vector<V> m_id;

    std::vector<std::vector<T>> m_comp;

    std::vector<std::vector<V>> m_g;
};

} // namespace zawa

#line 2 "Src/Graph/Components/BridgeTree.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/BridgeTree.hpp"

#include <concepts>
#include <vector>
#include <unordered_map>

namespace zawa {

template <std::integral T>
class BridgeTree {
public:

    using V = usize;

    BridgeTree() = default;

    explicit BridgeTree(const std::vector<std::vector<T>>& g) : m_id(g.size()) {
        const usize n = g.size();
        std::vector<usize> low(n), ord(n);
        std::vector<T> vs;
        std::vector<std::pair<T, T>> bridge;
        usize time = 1, id = 0;
        auto dfs = [&](auto dfs, T v, T p) -> void {
            low[v] = ord[v] = time++;
            std::unordered_map<T, usize> cnt;
            for (T x : g[v]) cnt[x]++;
            for (auto [x, c] : cnt) if (x != p) {
                if (ord[x]) {
                    low[v] = std::min(low[v], ord[x]);
                }
                else {
                    dfs(dfs, x, v);
                    low[v] = std::min(low[v], low[x]);
                    if (c == 1u and ord[v] < low[x]) {
                        std::vector<T> cur; 
                        while (vs.size() and low[x] <= low[vs.back()]) {
                            cur.push_back(vs.back());
                            m_id[vs.back()] = m_comp.size();
                            vs.pop_back();
                        }
                        bridge.emplace_back(x, v);
                        m_comp.push_back(std::move(cur));
                    }
                }
            }
            vs.push_back(v);
        };
        for (usize v = 0 ; v < n ; v++) if (!ord[v]) {
            dfs(dfs, v, static_cast<T>(-1));
            if (vs.size()) {
                std::vector<T> cur;
                while (vs.size()) {
                    m_id[vs.back()] = m_comp.size();
                    cur.push_back(vs.back());
                    vs.pop_back();
                }
                m_comp.push_back(std::move(cur));
            }
        }
        m_g.resize(m_comp.size());
        for (auto [u, v] : bridge) {
            const V p = m_id[u], q = m_id[v];
            m_g[p].push_back(q);
            m_g[q].push_back(p);
        }
    }

    inline usize size() const noexcept {
        return m_g.size();
    }

    const std::vector<V>& operator[](V v) const {
        assert(v < size());
        return m_g[v];
    }

    const std::vector<std::vector<T>>& components() const {
        return m_comp;
    }

    const std::vector<T>& component(V v) const {
        assert(v < size());
        return m_comp[v];
    }

private:

    std::vector<V> m_id;

    std::vector<std::vector<T>> m_comp;

    std::vector<std::vector<V>> m_g;
};

} // namespace zawa

Back to top page