block_cut_tree.hpp¶
把所有原顶点与点双分量组织成关联森林；保留分量顺序、自环单点块和孤立点。已有分解时线性构建；边集入口还需计入 lowlink 的分解开销。
Complexity: Time: \(O(V + B + I)\) from an existing decomposition, where \(B\) is the block count and \(I\) the sum of block sizes. An edge-list build additionally runs lowlink in \(O(V + E)\). Space: \(O(V + E + B + I)\).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + B + I) from an existing decomposition, where B is
/// the block count and I the sum of block sizes. An edge-list build additionally
/// runs lowlink in O(V + E). Space: O(V + E + B + I).
#include "noya/graph/lowlink.hpp"
#include <cassert>
#include <cstddef>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Block-cut incidence forest of an undirected multigraph. Original
/// vertices use ids [0, n), and block nodes use ids [n, n + blk.size()).
/// Preserves lowlink's block order, including one singleton per loop and one
/// block per isolated vertex. Requires n + blk.size() to fit in int.
struct block_cut_forest {
int n = 0;
std::vector<std::vector<int>> blk;
std::vector<std::vector<int>> tr;
std::vector<std::vector<int>> bel;
block_cut_forest() = default;
block_cut_forest(int n_, const std::vector<std::pair<int, int>> &es) {
build(n_, es);
}
explicit block_cut_forest(const lowlink &dec) {
build(dec);
}
/// @brief Rebuild the forest from an edge list.
void build(int n_, const std::vector<std::pair<int, int>> &es) {
// Move blocks from the temporary, destroying its other arrays before
// constructing the incidence forest.
blk = lowlink(n_, es).bcc;
n = n_;
build_incidence();
}
/// @brief Rebuild the forest from an existing lowlink dec.
void build(const lowlink &dec) {
n = dec.n;
blk = dec.bcc;
build_incidence();
}
int block_node(int bid) const {
assert(0 <= bid && bid < int(blk.size()));
return n + bid;
}
bool is_block_node(int nd) const {
assert(0 <= nd && nd < int(tr.size()));
return nd >= n;
}
private:
void build_incidence() {
assert(n >= 0 && blk.size() <= std::size_t(std::numeric_limits<int>::max() - n));
// Every tr row is overwritten below; resize preserves buffers on rebuild.
tr.resize(std::size_t(n) + blk.size());
bel.assign(n, {});
for (int bid = 0; bid < int(blk.size()); ++bid) {
tr[n + bid] = blk[bid];
for (int u : blk[bid]) {
assert(0 <= u && u < n);
bel[u].push_back(bid);
}
}
for (int u = 0; u < n; ++u) {
tr[u].resize(bel[u].size());
for (std::size_t i = 0; i < bel[u].size(); ++i)
tr[u][i] = n + bel[u][i];
}
}
};
} // namespace noya
// NOYA_BLOCK_CUT_TREE_HPP
#ifndef NOYA_BLOCK_CUT_TREE_HPP
#define NOYA_BLOCK_CUT_TREE_HPP 1
/// @complexity Time: O(V + B + I) from an existing decomposition, where B is
/// the block count and I the sum of block sizes. An edge-list build additionally
/// runs lowlink in O(V + E). Space: O(V + E + B + I).
#include "noya/graph/lowlink.hpp"
#include <cassert>
#include <cstddef>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Block-cut incidence forest of an undirected multigraph. Original
/// vertices use ids [0, n), and block nodes use ids [n, n + blk.size()).
/// Preserves lowlink's block order, including one singleton per loop and one
/// block per isolated vertex. Requires n + blk.size() to fit in int.
struct block_cut_forest {
int n = 0;
std::vector<std::vector<int>> blk;
std::vector<std::vector<int>> tr;
std::vector<std::vector<int>> bel;
block_cut_forest() = default;
block_cut_forest(int n_, const std::vector<std::pair<int, int>> &es) {
build(n_, es);
}
explicit block_cut_forest(const lowlink &dec) {
build(dec);
}
/// @brief Rebuild the forest from an edge list.
void build(int n_, const std::vector<std::pair<int, int>> &es) {
// Move blocks from the temporary, destroying its other arrays before
// constructing the incidence forest.
blk = lowlink(n_, es).bcc;
n = n_;
build_incidence();
}
/// @brief Rebuild the forest from an existing lowlink dec.
void build(const lowlink &dec) {
n = dec.n;
blk = dec.bcc;
build_incidence();
}
int block_node(int bid) const {
assert(0 <= bid && bid < int(blk.size()));
return n + bid;
}
bool is_block_node(int nd) const {
assert(0 <= nd && nd < int(tr.size()));
return nd >= n;
}
private:
void build_incidence() {
assert(n >= 0 && blk.size() <= std::size_t(std::numeric_limits<int>::max() - n));
// Every tr row is overwritten below; resize preserves buffers on rebuild.
tr.resize(std::size_t(n) + blk.size());
bel.assign(n, {});
for (int bid = 0; bid < int(blk.size()); ++bid) {
tr[n + bid] = blk[bid];
for (int u : blk[bid]) {
assert(0 <= u && u < n);
bel[u].push_back(bid);
}
}
for (int u = 0; u < n; ++u) {
tr[u].resize(bel[u].size());
for (std::size_t i = 0; i < bel[u].size(); ++i)
tr[u][i] = n + bel[u][i];
}
}
};
} // namespace noya
#endif // NOYA_BLOCK_CUT_TREE_HPP
/// @complexity Time: O(V + B + I) from an existing decomposition, where B is
/// the block count and I the sum of block sizes. An edge-list build additionally
/// runs lowlink in O(V + E). Space: O(V + E + B + I).
/// @complexity Time: O(V + E) build, O(1) is_bridge.
/// Space: O(V + E), including O(V) recursive DFS depth.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Lowlink decomposition of an undirected multigraph.
struct lowlink {
int n = 0;
std::vector<std::pair<int, int>> es;
std::vector<std::vector<std::pair<int, int>>> g;
std::vector<int> ord;
std::vector<int> low;
std::vector<bool> cut;
std::vector<int> bri;
std::vector<std::vector<int>> bcc;
std::vector<int> ecc;
int cnt = 0;
lowlink() = default;
lowlink(int n_, const std::vector<std::pair<int, int>> &es_) {
build(n_, es_);
}
/// @brief Rebuild cut points, bridges, vertex-biconnected
/// components, and two-edge-connected components.
void build(int n_, const std::vector<std::pair<int, int>> &es_) {
assert(n_ >= 0);
n = n_;
es = es_;
bool fresh = g.empty();
g.assign(n, {});
// Rebuilds already retain row capacity; reserve only for fresh adjacency.
if (fresh) {
std::vector<std::size_t> degree(n);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
++degree[u];
++degree[v];
}
for (int u = 0; u < n; ++u) g[u].reserve(degree[u]);
}
for (int id = 0; id < int(es.size()); ++id) {
auto [u, v] = es[id];
assert(0 <= u && u < n && 0 <= v && v < n);
g[u].emplace_back(v, id);
g[v].emplace_back(u, id);
}
ord.assign(n, -1);
low.assign(n, -1);
cut.assign(n, false);
ecc.assign(n, -1);
bri.clear();
bcc.clear();
cnt = 0;
int timer = 0;
std::vector<int> vertices, components;
std::vector<bool> bridge(es.size());
bool unordered = false;
auto dfs = [&](auto &self, int u, int pe, int root) -> void {
ord[u] = low[u] = timer++;
vertices.push_back(u);
components.push_back(u);
int children = 0;
for (auto [v, eid] : g[u]) {
if (eid == pe || u == v) continue;
if (ord[v] == -1) {
++children;
self(self, v, eid, root);
low[u] = std::min(low[u], low[v]);
if (low[v] > ord[u]) bridge[eid] = true;
if (low[v] >= ord[u]) {
if (u != root || children >= 2) cut[u] = true;
std::vector<int> block{u};
// Every non-root vertex is popped once; u may join several blocks.
for (;;) {
int x = vertices.back();
vertices.pop_back();
block.push_back(x);
if (x == v) break;
}
if (block.size() == 2) {
if (block[0] > block[1]) std::swap(block[0], block[1]);
} else {
unordered = true;
}
bcc.push_back(std::move(block));
}
} else {
low[u] = std::min(low[u], ord[v]);
}
}
// Closing a lowpoint root also completes one two-edge component.
if (low[u] == ord[u]) {
for (;;) {
int v = components.back();
components.pop_back();
ecc[v] = cnt;
if (v == u) break;
}
++cnt;
}
};
for (int root = 0; root < n; ++root) if (ord[root] == -1) {
dfs(dfs, root, -1, root);
vertices.pop_back();
if (g[root].empty()) bcc.push_back({root});
}
for (int id = 0; id < int(es.size()); ++id) {
auto [u, v] = es[id];
if (u == v) bcc.push_back({u});
if (bridge[id]) bri.push_back(id);
}
// Bucket memberships by vertex to sort block contents in linear time.
if (unordered) {
std::vector<std::size_t> begin(n);
std::size_t total = 0;
for (const auto &block : bcc) if (block.size() > 2)
for (int u : block) { ++begin[u]; ++total; }
std::partial_sum(begin.begin(), begin.end(), begin.begin());
std::vector<std::size_t> ids(total);
for (std::size_t b = 0; b < bcc.size(); ++b) if (bcc[b].size() > 2) {
for (int u : bcc[b]) ids[--begin[u]] = b;
bcc[b].clear();
}
for (int u = 0; u < n; ++u) {
std::size_t end = u + 1 < n ? begin[u + 1] : total;
for (std::size_t j = begin[u]; j < end; ++j) bcc[ids[j]].push_back(u);
}
}
// Preserve component IDs ordered by their minimum vertex.
std::vector<int> rename(cnt, -1);
int next = 0;
for (int &c : ecc) {
if (rename[c] < 0) rename[c] = next++;
c = rename[c];
}
}
/// @brief Return whether an input edge is a bridge, in O(1).
bool is_bridge(int eid) const {
assert(0 <= eid && eid < int(es.size()));
if (bri.empty()) return false;
auto [u, v] = es[eid];
if (ord[u] > ord[v]) std::swap(u, v);
return low[v] > ord[u];
}
};
} // namespace noya
#include <cassert>
#include <cstddef>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Block-cut incidence forest of an undirected multigraph. Original
/// vertices use ids [0, n), and block nodes use ids [n, n + blk.size()).
/// Preserves lowlink's block order, including one singleton per loop and one
/// block per isolated vertex. Requires n + blk.size() to fit in int.
struct block_cut_forest {
int n = 0;
std::vector<std::vector<int>> blk;
std::vector<std::vector<int>> tr;
std::vector<std::vector<int>> bel;
block_cut_forest() = default;
block_cut_forest(int n_, const std::vector<std::pair<int, int>> &es) {
build(n_, es);
}
explicit block_cut_forest(const lowlink &dec) {
build(dec);
}
/// @brief Rebuild the forest from an edge list.
void build(int n_, const std::vector<std::pair<int, int>> &es) {
// Move blocks from the temporary, destroying its other arrays before
// constructing the incidence forest.
blk = lowlink(n_, es).bcc;
n = n_;
build_incidence();
}
/// @brief Rebuild the forest from an existing lowlink dec.
void build(const lowlink &dec) {
n = dec.n;
blk = dec.bcc;
build_incidence();
}
int block_node(int bid) const {
assert(0 <= bid && bid < int(blk.size()));
return n + bid;
}
bool is_block_node(int nd) const {
assert(0 <= nd && nd < int(tr.size()));
return nd >= n;
}
private:
void build_incidence() {
assert(n >= 0 && blk.size() <= std::size_t(std::numeric_limits<int>::max() - n));
// Every tr row is overwritten below; resize preserves buffers on rebuild.
tr.resize(std::size_t(n) + blk.size());
bel.assign(n, {});
for (int bid = 0; bid < int(blk.size()); ++bid) {
tr[n + bid] = blk[bid];
for (int u : blk[bid]) {
assert(0 <= u && u < n);
bel[u].push_back(bid);
}
}
for (int u = 0; u < n; ++u) {
tr[u].resize(bel[u].size());
for (std::size_t i = 0; i < bel[u].size(); ++i)
tr[u][i] = n + bel[u][i];
}
}
};
} // namespace noya
// NOYA_BLOCK_CUT_TREE_HPP