graph/bcc.hpp

• View this file on GitHub
• Last update: 2025-03-28 03:08:58+09:00
• Include: #include "graph/bcc.hpp"

Depends on

• graph/lowlink.hpp

Required by

• graph/tree/block_cut_tree.hpp

Verified with

• verify/yosupo_graph/graph_bcc.test.cpp
• verify/yuki/yuki_1326.test.cpp

Code

#ifndef KK2_GRAPH_BCC_HPP
#define KK2_GRAPH_BCC_HPP 1

#include <functional>
#include <vector>

#include "lowlink.hpp"

namespace kk2 {

template <class G> struct BCC : LowLink<G> {
    BCC(const G &g_) : LowLink<G>(g_) { init_bcc(); }

    std::vector<std::vector<int>> group_e;
    std::vector<int> comp_e;

  private:
    void init_bcc() {
        comp_e = std::vector<int>(this->m, -1);
        auto add = [&](int ei, int k) {
            group_e[k].emplace_back(ei);
            comp_e[ei] = k;
        };
        auto dfs = [&](auto self, int u, int k = -1, int ei = -1) -> void {
            for (auto &e : this->g[u]) {
                if (e.id == ei) continue;
                if (this->used_on_dfs_tree[e.id]) {
                    int nk = k;
                    if (this->low[e.to] >= this->ord[u])
                        nk = group_e.size(), group_e.emplace_back();
                    add(e.id, nk);
                    self(self, e.to, nk, e.id);
                }
                // back edge
                else if (this->ord[e.to] < this->ord[u]) {
                    add(e.id, k);
                }
            }
        };
        for (int u = 0; u < this->n; u++)
            if (this->root[u]) { dfs(dfs, u); }
    }

  public:
    std::vector<std::vector<int>> get_bcc_vertices() {
        std::vector<bool> buf1(this->n), buf2(this->n);
        std::vector<std::vector<int>> res;
        res.reserve(group_e.size());
        for (auto &bc : group_e) {
            if (bc.empty()) continue;
            int k = (int)res.size();
            res.emplace_back();
            for (auto &ei : bc) {
                auto e = this->g.edges[ei];
                int fr = e.from, to = e.to;
                if (!buf2[fr]) {
                    res[k].emplace_back(fr);
                    buf2[fr] = true;
                }
                if (!buf2[to]) {
                    res[k].emplace_back(to);
                    buf2[to] = true;
                }
                buf1[fr] = buf1[to] = true;
            }
            for (auto &ei : bc) {
                auto e = this->g.edges[ei];
                int fr = e.from, to = e.to;
                buf2[fr] = buf2[to] = false;
            }
        }
        for (int i = 0; i < this->n; i++)
            if (!buf1[i]) {
                int k = (int)res.size();
                res.emplace_back();
                res[k].emplace_back(i);
            }
        return res;
    }
};

} // namespace kk2

#endif // KK2_GRAPH_BCC_HPP

#line 1 "graph/bcc.hpp"



#include <functional>
#include <vector>

#line 1 "graph/lowlink.hpp"



#include <algorithm>
#include <cassert>
#line 7 "graph/lowlink.hpp"
#include <type_traits>
#line 9 "graph/lowlink.hpp"

namespace kk2 {

template <class G> struct LowLink {
    static_assert(!G::directed, "LowLink requires undirected graph");

    int n, m;
    const G &g;
    std::vector<int> ord, low;
    std::vector<bool> root, used_on_dfs_tree;
    std::vector<int> bridges, articulations;

    LowLink(const G &g_)
        : n(g_.num_vertices()),
          m(g_.num_edges()),
          g(g_),
          ord(n, -1),
          low(n, -1),
          root(n, false),
          used_on_dfs_tree(m, false) {
        init();
    }

  private:
    // v is a child of u in DFS tree
    // edge(u, v) is a bridge <=> ord[u] < low[v]

    // u is an articulation point <=> (u is root and u has two or more children) or
    // there exists a v which is a child of u in DFS tree and ord[u] <= low[v]

    void init() {
        int k = 0;
        auto dfs = [&](auto self, int u, int ei = -1) -> int {
            low[u] = ord[u] = k++;
            bool is_articulation = false;
            int count = 0;
            for (auto &&e : g[u]) {
                if (e.id == ei) continue;
                if (ord[e.to] == -1) {
                    ++count;
                    used_on_dfs_tree[e.id] = true;
                    low[u] = std::min(low[u], self(self, e.to, e.id));
                    if (ei != -1 and ord[u] <= low[e.to]) is_articulation = true;
                    if (ord[u] < low[e.to]) bridges.emplace_back(e.id);
                }
                // back edge
                else if (ord[e.to] < ord[u]) {
                    low[u] = std::min(low[u], ord[e.to]);
                }
            }
            if (ei == -1 and count >= 2) is_articulation = true;
            if (is_articulation) articulations.emplace_back(u);
            return low[u];
        };
        for (int u = 0; u < n; u++)
            if (ord[u] == -1) {
                dfs(dfs, u);
                root[u] = true;
            }
    }
};

} // namespace kk2


#line 8 "graph/bcc.hpp"

namespace kk2 {

template <class G> struct BCC : LowLink<G> {
    BCC(const G &g_) : LowLink<G>(g_) { init_bcc(); }

    std::vector<std::vector<int>> group_e;
    std::vector<int> comp_e;

  private:
    void init_bcc() {
        comp_e = std::vector<int>(this->m, -1);
        auto add = [&](int ei, int k) {
            group_e[k].emplace_back(ei);
            comp_e[ei] = k;
        };
        auto dfs = [&](auto self, int u, int k = -1, int ei = -1) -> void {
            for (auto &e : this->g[u]) {
                if (e.id == ei) continue;
                if (this->used_on_dfs_tree[e.id]) {
                    int nk = k;
                    if (this->low[e.to] >= this->ord[u])
                        nk = group_e.size(), group_e.emplace_back();
                    add(e.id, nk);
                    self(self, e.to, nk, e.id);
                }
                // back edge
                else if (this->ord[e.to] < this->ord[u]) {
                    add(e.id, k);
                }
            }
        };
        for (int u = 0; u < this->n; u++)
            if (this->root[u]) { dfs(dfs, u); }
    }

  public:
    std::vector<std::vector<int>> get_bcc_vertices() {
        std::vector<bool> buf1(this->n), buf2(this->n);
        std::vector<std::vector<int>> res;
        res.reserve(group_e.size());
        for (auto &bc : group_e) {
            if (bc.empty()) continue;
            int k = (int)res.size();
            res.emplace_back();
            for (auto &ei : bc) {
                auto e = this->g.edges[ei];
                int fr = e.from, to = e.to;
                if (!buf2[fr]) {
                    res[k].emplace_back(fr);
                    buf2[fr] = true;
                }
                if (!buf2[to]) {
                    res[k].emplace_back(to);
                    buf2[to] = true;
                }
                buf1[fr] = buf1[to] = true;
            }
            for (auto &ei : bc) {
                auto e = this->g.edges[ei];
                int fr = e.from, to = e.to;
                buf2[fr] = buf2[to] = false;
            }
        }
        for (int i = 0; i < this->n; i++)
            if (!buf1[i]) {
                int k = (int)res.size();
                res.emplace_back();
                res[k].emplace_back(i);
            }
        return res;
    }
};

} // namespace kk2

Back to top page