Block-Cut tree (+ 二重頂点連結成分分解)
(Src/Graph/Components/BlockCutTree.hpp)

• View this file on GitHub
• Last update: 2025-06-10 18:57:15+09:00
• Include: #include "Src/Graph/Components/BlockCutTree.hpp"

概要

Block Cut Treeを構築します。

ここでも簡単に補足しておくと

• 二重頂点連結成分
• 関節点

を適切につないだ木のことをBlock-Cut Treeといいます。

二重頂点連結成分分解のライブラリを単体で持ってないので、これで代用してください。

ライブラリ

constructor

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

隣接リストを与える。Tはstd::integralを満たす必要がある。

size

inline usize size() const noexcept

BCTの頂点数を返します。

operator[]

const std::vector<T>& operator[](usize i) const {

BCTの頂点 $i$ の隣接リストを返します。

type

enum class Type {
    BLOCK,
    CUT
};

Type type(usize i) const;

BCTの頂点 $i$ がBlockを表す頂点ならばBlockCutTree<T>::Type::BLOCKを、関節点を表すならばBlockCutTree<T>::Type::CUTを返します。

blocks

const std::vector<std::vector<T>>& blocks() const;

二重頂点連結成分全部を返します。

block

const std::vector<T>& block(usize i) const;

BCTの頂点 $i$ に対応する二重頂点連結成分を返します。

cuts

const std::vector<T>& cuts() const;

関節点を全部返します。

cut

const T cut(usize i) const;

BCTの頂点 $i$ に対応する関節点を返します。

vertices

std::vector<T> vertices(usize i) const;

BCTの頂点 $i$ に対応する頂点の列を返します。これはconst参照では無くコピーされます

isCut

bool isCut(T v) const

元のグラフで $v$ が関節点だったかどうか判定します。

cutId

std::optional<usize> cutId(usize i) const;

元のグラフの頂点 $i$ が関節点だった場合、BCTの対応する頂点の番号を返します。そうでなければstd::nulloptを返します。

Depends on

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

Verified with

• Test/AOJ/3022.test.cpp
• Test/LC/biconnected_components.test.cpp

Code

#pragma once

#include <cassert>
#include <concepts>
#include <vector>
#include <optional>

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

namespace zawa {

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

    BlockCutTree() = default;

    explicit BlockCutTree(const std::vector<std::vector<T>>& g) : inv_(g.size()) {
        const usize n = g.size();
        std::vector<usize> low(n), ord(n), vs;
        usize time = 1;
        const T INVALID = static_cast<T>(-1);
        auto dfs = [&](auto dfs, T v, T p) -> void {
            low[v] = ord[v] = time++;
            if (g[v].empty()) {
                blocks_.push_back({T{v}});
                return;
            }
            usize deg = 0;
            bool cut = false;
            for (T x : g[v]) {
                if (ord[x]) {
                    low[v] = std::min(low[v], ord[x]);
                }
                else {
                    deg++;
                    dfs(dfs, x, v);
                    low[v] = std::min(low[v], low[x]);
                    if (low[x] >= ord[v]) {
                        std::vector<T> cur{v};
                        cut |= p != INVALID;
                        while (vs.size() and ord[vs.back()] >= ord[x]) {
                            cur.push_back(vs.back());
                            vs.pop_back();
                        }
                        blocks_.push_back(std::move(cur));
                    }
                }
            }
            cut |= p == INVALID and deg >= 2;
            if (cut) cuts_.push_back(v);
            vs.push_back(v);
        };
        for (T i = 0 ; i < static_cast<T>(n) ; i++) if (!ord[i]) 
            dfs(dfs, i, INVALID);
        const usize m = blocks_.size(), k = cuts_.size();
        for (usize i = 0 ; i < k ; i++) inv_[cuts_[i]] = m + i;
        g_.resize(m + k);
        for (usize i = 0 ; i < m ; i++) {
            for (T v : blocks_[i]) if (inv_[v] >= m) {
                g_[i].push_back(inv_[v]);
                g_[inv_[v]].push_back(i);
            }
        }
    }

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

    const std::vector<T>& operator[](usize i) const {
        assert(i < size());
        return g_[i];
    }

    enum class Type {
        BLOCK,
        CUT
    };

    Type type(usize i) const {
        assert(i < size());
        return i < blocks_.size() ? Type::BLOCK : Type::CUT;
    }

    const std::vector<std::vector<T>>& blocks() const {
        return blocks_;
    }

    const std::vector<T>& block(usize i) const {
        assert(i < size() and type(i) == Type::BLOCK);
        return blocks_[i];
    }

    const std::vector<T>& cuts() const {
        return cuts_;
    }

    const T cut(usize i) const {
        assert(i < size() and type(i) == Type::CUT);
        return cuts_[i - blocks_.size()];
    }

    std::vector<T> vertices(usize i) const {
        assert(i < size());
        return i < blocks_.size() ? 
            blocks_[i] : std::vector<T>{cuts_[i - blocks_.size()]};
    }

    bool isCut(T v) const {
        assert(v < static_cast<T>(inv_.size()));
        return inv_[v] >= blocks_.size();
    }

    std::optional<usize> cutId(usize i) const {
        assert(i < size());
        return isCut(i) ? std::optional<usize>{inv_[i]} : std::nullopt;
    }

private:

    std::vector<std::vector<T>> blocks_;

    std::vector<T> cuts_;

    std::vector<std::vector<T>> g_;

    std::vector<usize> inv_;
};

} // namespace zawa

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

#include <cassert>
#include <concepts>
#include <vector>
#include <optional>

#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 9 "Src/Graph/Components/BlockCutTree.hpp"

namespace zawa {

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

    BlockCutTree() = default;

    explicit BlockCutTree(const std::vector<std::vector<T>>& g) : inv_(g.size()) {
        const usize n = g.size();
        std::vector<usize> low(n), ord(n), vs;
        usize time = 1;
        const T INVALID = static_cast<T>(-1);
        auto dfs = [&](auto dfs, T v, T p) -> void {
            low[v] = ord[v] = time++;
            if (g[v].empty()) {
                blocks_.push_back({T{v}});
                return;
            }
            usize deg = 0;
            bool cut = false;
            for (T x : g[v]) {
                if (ord[x]) {
                    low[v] = std::min(low[v], ord[x]);
                }
                else {
                    deg++;
                    dfs(dfs, x, v);
                    low[v] = std::min(low[v], low[x]);
                    if (low[x] >= ord[v]) {
                        std::vector<T> cur{v};
                        cut |= p != INVALID;
                        while (vs.size() and ord[vs.back()] >= ord[x]) {
                            cur.push_back(vs.back());
                            vs.pop_back();
                        }
                        blocks_.push_back(std::move(cur));
                    }
                }
            }
            cut |= p == INVALID and deg >= 2;
            if (cut) cuts_.push_back(v);
            vs.push_back(v);
        };
        for (T i = 0 ; i < static_cast<T>(n) ; i++) if (!ord[i]) 
            dfs(dfs, i, INVALID);
        const usize m = blocks_.size(), k = cuts_.size();
        for (usize i = 0 ; i < k ; i++) inv_[cuts_[i]] = m + i;
        g_.resize(m + k);
        for (usize i = 0 ; i < m ; i++) {
            for (T v : blocks_[i]) if (inv_[v] >= m) {
                g_[i].push_back(inv_[v]);
                g_[inv_[v]].push_back(i);
            }
        }
    }

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

    const std::vector<T>& operator[](usize i) const {
        assert(i < size());
        return g_[i];
    }

    enum class Type {
        BLOCK,
        CUT
    };

    Type type(usize i) const {
        assert(i < size());
        return i < blocks_.size() ? Type::BLOCK : Type::CUT;
    }

    const std::vector<std::vector<T>>& blocks() const {
        return blocks_;
    }

    const std::vector<T>& block(usize i) const {
        assert(i < size() and type(i) == Type::BLOCK);
        return blocks_[i];
    }

    const std::vector<T>& cuts() const {
        return cuts_;
    }

    const T cut(usize i) const {
        assert(i < size() and type(i) == Type::CUT);
        return cuts_[i - blocks_.size()];
    }

    std::vector<T> vertices(usize i) const {
        assert(i < size());
        return i < blocks_.size() ? 
            blocks_[i] : std::vector<T>{cuts_[i - blocks_.size()]};
    }

    bool isCut(T v) const {
        assert(v < static_cast<T>(inv_.size()));
        return inv_[v] >= blocks_.size();
    }

    std::optional<usize> cutId(usize i) const {
        assert(i < size());
        return isCut(i) ? std::optional<usize>{inv_[i]} : std::nullopt;
    }

private:

    std::vector<std::vector<T>> blocks_;

    std::vector<T> cuts_;

    std::vector<std::vector<T>> g_;

    std::vector<usize> inv_;
};

} // namespace zawa

Back to top page