block_cut_tree.hpp¶
Block-cut incidence forest of an undirected multigraph. Original vertices use ids [0, n), and block nodes use ids [n, n + blocks.size()).
把无向图的点双连通分量与割点组织成圆方树；便于将经过割点的路径问题转成树问题。
Implementation¶
#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 + blocks.size()).
struct block_cut_forest {
int n = 0;
std::vector<std::vector<int>> blocks;
std::vector<std::vector<int>> tree;
std::vector<std::vector<int>> vertex_blocks;
block_cut_forest() = default;
block_cut_forest(int n_, const std::vector<std::pair<int, int>> &edges) {
build(n_, edges);
}
explicit block_cut_forest(const lowlink &decomposition) {
build(decomposition);
}
/// @brief Rebuild the forest from an edge list.
void build(int n_, const std::vector<std::pair<int, int>> &edges) {
build(lowlink(n_, edges));
}
/// @brief Rebuild the forest from an existing lowlink decomposition.
void build(const lowlink &decomposition) {
n = decomposition.n;
blocks = decomposition.biconnected_components;
tree.assign(n + blocks.size(), {});
vertex_blocks.assign(n, {});
for (int block_id = 0; block_id < int(blocks.size()); block_id++) {
int node = block_node(block_id);
for (int vertex : blocks[block_id]) {
assert(0 <= vertex && vertex < n);
tree[vertex].push_back(node);
tree[node].push_back(vertex);
vertex_blocks[vertex].push_back(block_id);
}
}
}
int block_node(int block_id) const {
assert(0 <= block_id && block_id < int(blocks.size()));
return n + block_id;
}
bool is_block_node(int node) const {
assert(0 <= node && node < int(tree.size()));
return node >= 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>> edges;
std::vector<std::vector<std::pair<int, int>>> graph;
std::vector<int> ord;
std::vector<int> low;
std::vector<bool> articulation;
std::vector<int> bridge_ids;
std::vector<std::vector<int>> biconnected_components;
std::vector<int> two_edge_component;
int two_edge_component_count = 0;
lowlink() = default;
lowlink(int n_, const std::vector<std::pair<int, int>> &edges_) {
build(n_, edges_);
}
/// @brief Rebuild articulation points, bridges, vertex-biconnected
/// components, and two-edge-connected components.
void build(int n_, const std::vector<std::pair<int, int>> &edges_) {
assert(n_ >= 0);
n = n_;
edges = edges_;
graph.assign(n, {});
for (int id = 0; id < int(edges.size()); id++) {
auto [u, v] = edges[id];
assert(0 <= u && u < n);
assert(0 <= v && v < n);
graph[u].emplace_back(v, id);
graph[v].emplace_back(u, id);
}
ord.assign(n, -1);
low.assign(n, -1);
articulation.assign(n, false);
bridge_ids.clear();
biconnected_components.clear();
timer = 0;
edge_stack.clear();
for (int root = 0; root < n; root++) {
if (ord[root] == -1) {
dfs(root, -1, root);
if (graph[root].empty()) {
biconnected_components.push_back({root});
}
}
}
for (auto [u, v] : edges) {
if (u == v) {
biconnected_components.push_back({u});
}
}
std::sort(bridge_ids.begin(), bridge_ids.end());
build_two_edge_components();
}
/// @brief Return whether an input edge is a bridge.
bool is_bridge(int edge_id) const {
assert(0 <= edge_id && edge_id < int(edges.size()));
return std::binary_search(bridge_ids.begin(), bridge_ids.end(), edge_id);
}
private:
int timer = 0;
std::vector<int> edge_stack;
void dfs(int u, int parent_edge, int root) {
ord[u] = low[u] = timer++;
int child_count = 0;
for (auto [v, edge_id] : graph[u]) {
if (edge_id == parent_edge || u == v) {
continue;
}
if (ord[v] == -1) {
child_count++;
edge_stack.push_back(edge_id);
dfs(v, edge_id, root);
low[u] = std::min(low[u], low[v]);
if (low[v] > ord[u]) {
bridge_ids.push_back(edge_id);
}
if (low[v] >= ord[u]) {
if (u != root || child_count >= 2) {
articulation[u] = true;
}
std::vector<int> vertices;
while (true) {
int id = edge_stack.back();
edge_stack.pop_back();
vertices.push_back(edges[id].first);
vertices.push_back(edges[id].second);
if (id == edge_id) {
break;
}
}
std::sort(vertices.begin(), vertices.end());
vertices.erase(std::unique(vertices.begin(), vertices.end()),
vertices.end());
biconnected_components.push_back(std::move(vertices));
}
} else if (ord[v] < ord[u]) {
edge_stack.push_back(edge_id);
low[u] = std::min(low[u], ord[v]);
}
}
}
void build_two_edge_components() {
std::vector<bool> bridge(edges.size());
for (int id : bridge_ids) {
bridge[id] = true;
}
two_edge_component.assign(n, -1);
two_edge_component_count = 0;
std::vector<int> stack;
for (int start = 0; start < n; start++) {
if (two_edge_component[start] != -1) {
continue;
}
two_edge_component[start] = two_edge_component_count;
stack.push_back(start);
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
for (auto [v, edge_id] : graph[u]) {
if (!bridge[edge_id] && two_edge_component[v] == -1) {
two_edge_component[v] = two_edge_component_count;
stack.push_back(v);
}
}
}
two_edge_component_count++;
}
}
};
} // 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 + blocks.size()).
struct block_cut_forest {
int n = 0;
std::vector<std::vector<int>> blocks;
std::vector<std::vector<int>> tree;
std::vector<std::vector<int>> vertex_blocks;
block_cut_forest() = default;
block_cut_forest(int n_, const std::vector<std::pair<int, int>> &edges) {
build(n_, edges);
}
explicit block_cut_forest(const lowlink &decomposition) {
build(decomposition);
}
/// @brief Rebuild the forest from an edge list.
void build(int n_, const std::vector<std::pair<int, int>> &edges) {
build(lowlink(n_, edges));
}
/// @brief Rebuild the forest from an existing lowlink decomposition.
void build(const lowlink &decomposition) {
n = decomposition.n;
blocks = decomposition.biconnected_components;
tree.assign(n + blocks.size(), {});
vertex_blocks.assign(n, {});
for (int block_id = 0; block_id < int(blocks.size()); block_id++) {
int node = block_node(block_id);
for (int vertex : blocks[block_id]) {
assert(0 <= vertex && vertex < n);
tree[vertex].push_back(node);
tree[node].push_back(vertex);
vertex_blocks[vertex].push_back(block_id);
}
}
}
int block_node(int block_id) const {
assert(0 <= block_id && block_id < int(blocks.size()));
return n + block_id;
}
bool is_block_node(int node) const {
assert(0 <= node && node < int(tree.size()));
return node >= n;
}
};
} // namespace noya