block_cut_tree.hpp¶
把无向图的点双连通分量与割点组织成圆方树；便于将经过割点的路径问题转成树问题。
Complexity: Time: O(V + E). Space: O(V + E).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include "noya/lowlink.hpp"
#include <cassert>
#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()).
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) {
build(lowlink(n_, es));
}
/// @brief Rebuild the forest from an existing lowlink dec.
void build(const lowlink &dec) {
n = dec.n;
blk = dec.bcc;
tr.assign(n + blk.size(), {});
bel.assign(n, {});
for (int bid = 0; bid < int(blk.size()); bid++) {
int nd = block_node(bid);
for (int u : blk[bid]) {
assert(0 <= u && u < n);
tr[u].push_back(nd);
tr[nd].push_back(u);
bel[u].push_back(bid);
}
}
}
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;
}
};
} // namespace noya
#ifndef NOYA_BLOCK_CUT_TREE_HPP
#define NOYA_BLOCK_CUT_TREE_HPP 1
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include "noya/lowlink.hpp"
#include <cassert>
#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()).
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) {
build(lowlink(n_, es));
}
/// @brief Rebuild the forest from an existing lowlink dec.
void build(const lowlink &dec) {
n = dec.n;
blk = dec.bcc;
tr.assign(n + blk.size(), {});
bel.assign(n, {});
for (int bid = 0; bid < int(blk.size()); bid++) {
int nd = block_node(bid);
for (int u : blk[bid]) {
assert(0 <= u && u < n);
tr[u].push_back(nd);
tr[nd].push_back(u);
bel[u].push_back(bid);
}
}
}
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;
}
};
} // namespace noya
#endif // NOYA_BLOCK_CUT_TREE_HPP
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
/// @complexity Time: O(V + E).
/// Space: O(V + E).
/// @complexity Time: O(V + E).
/// Space: O(V + E).
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_;
g.assign(n, {});
for (int id = 0; id < int(es.size()); id++) {
auto [u, v] = es[id];
assert(0 <= u && u < n);
assert(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);
bri.clear();
bcc.clear();
tim = 0;
es1.clear();
for (int rt = 0; rt < n; rt++) {
if (ord[rt] == -1) {
dfs(rt, -1, rt);
if (g[rt].empty()) {
bcc.push_back({rt});
}
}
}
for (auto [u, v] : es) {
if (u == v) {
bcc.push_back({u});
}
}
std::sort(bri.begin(), bri.end());
build_two_edge_components();
}
/// @brief Return whether an input edge is a bridge.
bool is_bridge(int eid) const {
assert(0 <= eid && eid < int(es.size()));
return std::binary_search(bri.begin(), bri.end(), eid);
}
private:
int tim = 0;
std::vector<int> es1;
void dfs(int u, int pe, int rt) {
ord[u] = low[u] = tim++;
int num = 0;
for (auto [v, eid] : g[u]) {
if (eid == pe || u == v) {
continue;
}
if (ord[v] == -1) {
num++;
es1.push_back(eid);
dfs(v, eid, rt);
low[u] = std::min(low[u], low[v]);
if (low[v] > ord[u]) {
bri.push_back(eid);
}
if (low[v] >= ord[u]) {
if (u != rt || num >= 2) {
cut[u] = true;
}
std::vector<int> vs;
while (true) {
int id = es1.back();
es1.pop_back();
vs.push_back(es[id].first);
vs.push_back(es[id].second);
if (id == eid) {
break;
}
}
std::sort(vs.begin(), vs.end());
vs.erase(std::unique(vs.begin(), vs.end()), vs.end());
bcc.push_back(std::move(vs));
}
} else if (ord[v] < ord[u]) {
es1.push_back(eid);
low[u] = std::min(low[u], ord[v]);
}
}
}
void build_two_edge_components() {
std::vector<bool> br1(es.size());
for (int id : bri) {
br1[id] = true;
}
ecc.assign(n, -1);
cnt = 0;
std::vector<int> stk;
for (int s = 0; s < n; s++) {
if (ecc[s] != -1) {
continue;
}
ecc[s] = cnt;
stk.push_back(s);
while (!stk.empty()) {
int u = stk.back();
stk.pop_back();
for (auto [v, eid] : g[u]) {
if (!br1[eid] && ecc[v] == -1) {
ecc[v] = cnt;
stk.push_back(v);
}
}
}
cnt++;
}
}
};
} // namespace noya
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()).
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) {
build(lowlink(n_, es));
}
/// @brief Rebuild the forest from an existing lowlink dec.
void build(const lowlink &dec) {
n = dec.n;
blk = dec.bcc;
tr.assign(n + blk.size(), {});
bel.assign(n, {});
for (int bid = 0; bid < int(blk.size()); bid++) {
int nd = block_node(bid);
for (int u : blk[bid]) {
assert(0 <= u && u < n);
tr[u].push_back(nd);
tr[nd].push_back(u);
bel[u].push_back(bid);
}
}
}
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;
}
};
} // namespace noya