lowlink.hpp¶
Lowlink decomposition of an undirected multigraph.
Verified by biconnected_components, two_edge_connected_components.
求无向图的割点、桥以及 DFS lowlink 信息；用于删除单点或单边后的连通性分析。
Implementation¶
#ifndef NOYA_LOWLINK_HPP
#define NOYA_LOWLINK_HPP 1
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
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
#endif // NOYA_LOWLINK_HPP
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
/// @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