Biconnected Components
(graph/biconnected_components.hpp)

• View this file on GitHub
• Last update: 2025-02-21 23:59:41+09:00
• Include: #include "graph/biconnected_components.hpp"

Description

二重頂点連結成分は，どの1頂点を取り除いても連結であるような部分グラフである．つまり，関節点を含まない部分グラフである．

関節点と二重頂点連結成分を結んで構成した木は block cut tree と呼ばれる．

空間計算量: $O(V + E)$

Operations

• vector<vector<int>> biconnected_components(vector<vector<int>> G, Lowlink low)
  • グラフ $G$ の隣接リストと，$G$ の lowlink 構造体が与えられたとき，$G$ を二重頂点連結成分分解する．$G$ の二重頂点連結成分を返す
  • 時間計算量: $O(V + E)$
• vector<vector<int>> block_cut_tree(vector<vector<int>> blocks, vector<int> cuts)
  • ブロック（二重頂点連結成分）とカット（関節点）のリストが与えられたときに，対応する block cut tree の隣接リストを返す
  • 時間計算量: $O(B + C)$

Depends on

• Lowlink (graph/lowlink.hpp)

Verified with

• test/yosupo/biconnected_components.test.cpp

Code

#pragma once
#include <set>
#include <stack>
#include <unordered_map>
#include <utility>
#include <vector>

#include "lowlink.hpp"

std::vector<std::vector<int>> biconnected_components(
    const std::vector<std::vector<int>>& G, const Lowlink& low) {
    std::vector<bool> used(G.size());
    std::stack<std::pair<int, int>> st;
    std::vector<std::vector<int>> blocks;

    auto dfs = [&](auto& dfs, int v, int p) -> void {
        used[v] = true;
        for (int c : G[v]) {
            if (c == p) continue;
            if (!used[c] || low.ord[c] < low.ord[v]) {
                st.emplace(v, c);
            }
            if (!used[c]) {
                dfs(dfs, c, v);
                if (low.ord[v] <= low.low[c]) {  // v is an articulation point
                    std::set<int> block;
                    while (true) {
                        auto e = st.top();
                        st.pop();
                        block.insert(e.first);
                        block.insert(e.second);
                        if (e.first == v) {
                            break;
                        }
                    }
                    blocks.emplace_back(block.begin(), block.end());
                }
            }
        }
    };

    for (int v = 0; v < (int)G.size(); ++v) {
        if (!used[v]) dfs(dfs, v, -1);
        if (G[v].empty()) {
            blocks.push_back({v});
        }
    }

    return blocks;
}

// B: number of blocks, C: number of cut vertices
// 0 through B - 1: block
// B through B + C - 1: cut
std::vector<std::vector<int>> block_cut_tree(
    const std::vector<std::vector<int>>& blocks, const std::vector<int>& cuts) {
    const int B = blocks.size();
    std::vector<std::vector<int>> bct(B + (int)cuts.size());
    std::unordered_map<int, int> cut_idx;
    for (int i = 0; i < (int)cuts.size(); ++i) cut_idx[cuts[i]] = i;

    for (int i = 0; i < (int)blocks.size(); ++i) {
        auto& block = blocks[i];
        for (int v : block) {
            if (cut_idx.contains(v)) {
                int j = B + cut_idx[v];
                bct[i].push_back(j);
                bct[j].push_back(i);
            }
        }
    }

    return bct;
}

#line 2 "graph/biconnected_components.hpp"
#include <set>
#include <stack>
#include <unordered_map>
#include <utility>
#include <vector>

#line 2 "graph/lowlink.hpp"
#include <algorithm>
#line 5 "graph/lowlink.hpp"

class Lowlink {
   public:
    std::vector<int> ord, low;
    std::vector<std::pair<int, int>> bridge;
    std::vector<int> articulation;

    Lowlink() = default;
    explicit Lowlink(const std::vector<std::vector<int>>& G)
        : ord(G.size(), -1), low(G.size()), G(G) {
        for (int i = 0; i < (int)G.size(); ++i) {
            if (ord[i] == -1) dfs(i, -1);
        }
    }

    bool is_bridge(int u, int v) const {
        if (ord[u] > ord[v]) std::swap(u, v);
        return ord[u] < low[v];
    }

   private:
    std::vector<std::vector<int>> G;
    int k = 0;

    void dfs(int v, int p) {
        low[v] = ord[v] = k++;
        bool is_articulation = false, checked = false;
        int cnt = 0;
        for (int c : G[v]) {
            if (c == p && !checked) {
                checked = true;
                continue;
            }
            if (ord[c] == -1) {
                ++cnt;
                dfs(c, v);
                low[v] = std::min(low[v], low[c]);
                if (p != -1 && ord[v] <= low[c]) is_articulation = true;
                if (ord[v] < low[c]) bridge.push_back(std::minmax(v, c));
            } else {
                low[v] = std::min(low[v], ord[c]);
            }
        }
        if (p == -1 && cnt > 1) is_articulation = true;
        if (is_articulation) articulation.push_back(v);
    }
};
#line 9 "graph/biconnected_components.hpp"

std::vector<std::vector<int>> biconnected_components(
    const std::vector<std::vector<int>>& G, const Lowlink& low) {
    std::vector<bool> used(G.size());
    std::stack<std::pair<int, int>> st;
    std::vector<std::vector<int>> blocks;

    auto dfs = [&](auto& dfs, int v, int p) -> void {
        used[v] = true;
        for (int c : G[v]) {
            if (c == p) continue;
            if (!used[c] || low.ord[c] < low.ord[v]) {
                st.emplace(v, c);
            }
            if (!used[c]) {
                dfs(dfs, c, v);
                if (low.ord[v] <= low.low[c]) {  // v is an articulation point
                    std::set<int> block;
                    while (true) {
                        auto e = st.top();
                        st.pop();
                        block.insert(e.first);
                        block.insert(e.second);
                        if (e.first == v) {
                            break;
                        }
                    }
                    blocks.emplace_back(block.begin(), block.end());
                }
            }
        }
    };

    for (int v = 0; v < (int)G.size(); ++v) {
        if (!used[v]) dfs(dfs, v, -1);
        if (G[v].empty()) {
            blocks.push_back({v});
        }
    }

    return blocks;
}

// B: number of blocks, C: number of cut vertices
// 0 through B - 1: block
// B through B + C - 1: cut
std::vector<std::vector<int>> block_cut_tree(
    const std::vector<std::vector<int>>& blocks, const std::vector<int>& cuts) {
    const int B = blocks.size();
    std::vector<std::vector<int>> bct(B + (int)cuts.size());
    std::unordered_map<int, int> cut_idx;
    for (int i = 0; i < (int)cuts.size(); ++i) cut_idx[cuts[i]] = i;

    for (int i = 0; i < (int)blocks.size(); ++i) {
        auto& block = blocks[i];
        for (int v : block) {
            if (cut_idx.contains(v)) {
                int j = B + cut_idx[v];
                bct[i].push_back(j);
                bct[j].push_back(i);
            }
        }
    }

    return bct;
}

Back to top page