lowlink.hpp¶
求无向图的割点、桥以及 DFS lowlink 信息；用于删除单点或单边后的连通性分析。
Complexity: Time: \(O(V + E)\) build, \(O(1)\) is_bridge. Space: \(O(V + E)\), including \(O(V)\) recursive DFS depth.
AC 记录：biconnected_components, two_edge_connected_components。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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
// NOYA_LOWLINK_HPP
#ifndef NOYA_LOWLINK_HPP
#define NOYA_LOWLINK_HPP 1
/// @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
#endif // NOYA_LOWLINK_HPP
/// @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
// NOYA_LOWLINK_HPP