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