three_edge_connected_components.hpp¶
求无向多重图中删去至多两条边后仍互相连通的极大点集；连通性按原图路径判断，允许自环重边。保留线性链合并算法，用泛型 lambda 递归并保留紧凑位标记。
Complexity: Time: \(O(n + m)\). Space: \(O(n)\) auxiliary, excluding the input adjacency lists.
Source: noshi91
AC 记录：three_edge_connected_components。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n + m).
/// Space: O(n) auxiliary, excluding the input adjacency lists.
#include <algorithm>
#include <cassert>
#include <limits>
#include <numeric>
#include <vector>
namespace noya {
namespace three_edge_connected_components_internal {
class circular_partition {
std::vector<int> nx_;
public:
explicit circular_partition(int siz) : nx_(siz) {
std::iota(nx_.begin(), nx_.end(), 0);
}
void merge(int a, int b) {
assert(0 <= a && a < int(nx_.size()));
assert(0 <= b && b < int(nx_.size()));
std::swap(nx_[a], nx_[b]);
}
std::vector<std::vector<int>> groups() const {
std::vector<std::vector<int>> res;
std::vector<bool> vis(nx_.size());
for (int s = 0; s < int(nx_.size()); s++) {
if (vis[s]) {
continue;
}
res.emplace_back();
int u = s;
do {
vis[u] = true;
res.back().push_back(u);
u = nx_[u];
} while (u != s);
}
return res;
}
};
} // namespace three_edge_connected_components_internal
/// @brief Decompose an undirected multigraph into maximal vertex sets that
/// remain mutually connected after deleting up to two edges. The DFS maintains
/// for each active subtree its earliest back-edge endpoint, the net number of
/// upward paths, and a linked chain of unfinished pieces. Whenever a chain can
/// no longer be separated by a cut of size at most two, its circular lists are
/// spliced in O(1). Each vertex and edge enters and leaves a chain once.
/// Non-loop adjacency entries must have matching reverse multiplicities;
/// loops are ignored. Empty/disconnected graphs and parallel edges are allowed.
/// Vertex count and total adjacency entries must fit int; endpoints are valid.
/// Inputs are unchanged. Components start at their minimum vertex and appear
/// in increasing minimum order; other members retain circular merge order.
/// Connectivity is measured in the whole graph, not in each induced subgraph.
/// Recursive depth can be O(n); local tests use 512 MiB stacks.
inline std::vector<std::vector<int>>
three_edge_connected_components(const std::vector<std::vector<int>> &g) {
using three_edge_connected_components_internal::circular_partition;
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
int n = int(g.size());
std::size_t entries = 0;
for (const auto &row : g) {
assert(row.size() <= std::size_t(std::numeric_limits<int>::max()) - entries);
entries += row.size();
}
std::vector<int> in(n);
std::vector<int> out(n);
std::vector<int> low(n, n);
std::vector<int> deg(n);
std::vector<int> pth(n, n);
std::vector<bool> vis(n);
circular_partition dsu(n);
int tim = 0;
auto abs = [&](int u, int v) {
dsu.merge(u, v);
deg[u] += deg[v];
};
auto dfs = [&](auto &self, int u, int fa) -> void {
vis[u] = true;
in[u] = tim++;
for (int x : g[u]) {
assert(0 <= x && x < n);
if (x == u) {
continue;
}
if (x == fa) {
fa = n;
continue;
}
if (vis[x]) {
if (in[x] < in[u]) {
deg[u]++;
low[u] = std::min(low[u], in[x]);
} else {
deg[u]--;
int ch = pth[u];
while (ch != n && in[ch] <= in[x] && in[x] < out[ch]) {
abs(u, ch);
ch = pth[ch];
}
pth[u] = ch;
}
continue;
}
self(self, x, u);
if (pth[x] == n && deg[x] <= 1) {
deg[u] += deg[x];
low[u] = std::min(low[u], low[x]);
continue;
}
if (deg[x] == 0) {
x = pth[x];
}
if (low[x] < low[u]) {
low[u] = low[x];
std::swap(x, pth[u]);
}
while (x != n) {
abs(u, x);
x = pth[x];
}
}
out[u] = tim;
};
for (int u = 0; u < n; u++) {
if (!vis[u]) {
dfs(dfs, u, n);
}
}
return dsu.groups();
}
} // namespace noya
// NOYA_THREE_EDGE_CONNECTED_COMPONENTS_HPP
#ifndef NOYA_THREE_EDGE_CONNECTED_COMPONENTS_HPP
#define NOYA_THREE_EDGE_CONNECTED_COMPONENTS_HPP 1
/// @complexity Time: O(n + m).
/// Space: O(n) auxiliary, excluding the input adjacency lists.
#include <algorithm>
#include <cassert>
#include <limits>
#include <numeric>
#include <vector>
namespace noya {
namespace three_edge_connected_components_internal {
class circular_partition {
std::vector<int> nx_;
public:
explicit circular_partition(int siz) : nx_(siz) {
std::iota(nx_.begin(), nx_.end(), 0);
}
void merge(int a, int b) {
assert(0 <= a && a < int(nx_.size()));
assert(0 <= b && b < int(nx_.size()));
std::swap(nx_[a], nx_[b]);
}
std::vector<std::vector<int>> groups() const {
std::vector<std::vector<int>> res;
std::vector<bool> vis(nx_.size());
for (int s = 0; s < int(nx_.size()); s++) {
if (vis[s]) {
continue;
}
res.emplace_back();
int u = s;
do {
vis[u] = true;
res.back().push_back(u);
u = nx_[u];
} while (u != s);
}
return res;
}
};
} // namespace three_edge_connected_components_internal
/// @brief Decompose an undirected multigraph into maximal vertex sets that
/// remain mutually connected after deleting up to two edges. The DFS maintains
/// for each active subtree its earliest back-edge endpoint, the net number of
/// upward paths, and a linked chain of unfinished pieces. Whenever a chain can
/// no longer be separated by a cut of size at most two, its circular lists are
/// spliced in O(1). Each vertex and edge enters and leaves a chain once.
/// Non-loop adjacency entries must have matching reverse multiplicities;
/// loops are ignored. Empty/disconnected graphs and parallel edges are allowed.
/// Vertex count and total adjacency entries must fit int; endpoints are valid.
/// Inputs are unchanged. Components start at their minimum vertex and appear
/// in increasing minimum order; other members retain circular merge order.
/// Connectivity is measured in the whole graph, not in each induced subgraph.
/// Recursive depth can be O(n); local tests use 512 MiB stacks.
inline std::vector<std::vector<int>>
three_edge_connected_components(const std::vector<std::vector<int>> &g) {
using three_edge_connected_components_internal::circular_partition;
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
int n = int(g.size());
std::size_t entries = 0;
for (const auto &row : g) {
assert(row.size() <= std::size_t(std::numeric_limits<int>::max()) - entries);
entries += row.size();
}
std::vector<int> in(n);
std::vector<int> out(n);
std::vector<int> low(n, n);
std::vector<int> deg(n);
std::vector<int> pth(n, n);
std::vector<bool> vis(n);
circular_partition dsu(n);
int tim = 0;
auto abs = [&](int u, int v) {
dsu.merge(u, v);
deg[u] += deg[v];
};
auto dfs = [&](auto &self, int u, int fa) -> void {
vis[u] = true;
in[u] = tim++;
for (int x : g[u]) {
assert(0 <= x && x < n);
if (x == u) {
continue;
}
if (x == fa) {
fa = n;
continue;
}
if (vis[x]) {
if (in[x] < in[u]) {
deg[u]++;
low[u] = std::min(low[u], in[x]);
} else {
deg[u]--;
int ch = pth[u];
while (ch != n && in[ch] <= in[x] && in[x] < out[ch]) {
abs(u, ch);
ch = pth[ch];
}
pth[u] = ch;
}
continue;
}
self(self, x, u);
if (pth[x] == n && deg[x] <= 1) {
deg[u] += deg[x];
low[u] = std::min(low[u], low[x]);
continue;
}
if (deg[x] == 0) {
x = pth[x];
}
if (low[x] < low[u]) {
low[u] = low[x];
std::swap(x, pth[u]);
}
while (x != n) {
abs(u, x);
x = pth[x];
}
}
out[u] = tim;
};
for (int u = 0; u < n; u++) {
if (!vis[u]) {
dfs(dfs, u, n);
}
}
return dsu.groups();
}
} // namespace noya
#endif // NOYA_THREE_EDGE_CONNECTED_COMPONENTS_HPP
/// @complexity Time: O(n + m).
/// Space: O(n) auxiliary, excluding the input adjacency lists.
#include <algorithm>
#include <cassert>
#include <limits>
#include <numeric>
#include <vector>
namespace noya {
namespace three_edge_connected_components_internal {
class circular_partition {
std::vector<int> nx_;
public:
explicit circular_partition(int siz) : nx_(siz) {
std::iota(nx_.begin(), nx_.end(), 0);
}
void merge(int a, int b) {
assert(0 <= a && a < int(nx_.size()));
assert(0 <= b && b < int(nx_.size()));
std::swap(nx_[a], nx_[b]);
}
std::vector<std::vector<int>> groups() const {
std::vector<std::vector<int>> res;
std::vector<bool> vis(nx_.size());
for (int s = 0; s < int(nx_.size()); s++) {
if (vis[s]) {
continue;
}
res.emplace_back();
int u = s;
do {
vis[u] = true;
res.back().push_back(u);
u = nx_[u];
} while (u != s);
}
return res;
}
};
} // namespace three_edge_connected_components_internal
/// @brief Decompose an undirected multigraph into maximal vertex sets that
/// remain mutually connected after deleting up to two edges. The DFS maintains
/// for each active subtree its earliest back-edge endpoint, the net number of
/// upward paths, and a linked chain of unfinished pieces. Whenever a chain can
/// no longer be separated by a cut of size at most two, its circular lists are
/// spliced in O(1). Each vertex and edge enters and leaves a chain once.
/// Non-loop adjacency entries must have matching reverse multiplicities;
/// loops are ignored. Empty/disconnected graphs and parallel edges are allowed.
/// Vertex count and total adjacency entries must fit int; endpoints are valid.
/// Inputs are unchanged. Components start at their minimum vertex and appear
/// in increasing minimum order; other members retain circular merge order.
/// Connectivity is measured in the whole graph, not in each induced subgraph.
/// Recursive depth can be O(n); local tests use 512 MiB stacks.
inline std::vector<std::vector<int>>
three_edge_connected_components(const std::vector<std::vector<int>> &g) {
using three_edge_connected_components_internal::circular_partition;
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
int n = int(g.size());
std::size_t entries = 0;
for (const auto &row : g) {
assert(row.size() <= std::size_t(std::numeric_limits<int>::max()) - entries);
entries += row.size();
}
std::vector<int> in(n);
std::vector<int> out(n);
std::vector<int> low(n, n);
std::vector<int> deg(n);
std::vector<int> pth(n, n);
std::vector<bool> vis(n);
circular_partition dsu(n);
int tim = 0;
auto abs = [&](int u, int v) {
dsu.merge(u, v);
deg[u] += deg[v];
};
auto dfs = [&](auto &self, int u, int fa) -> void {
vis[u] = true;
in[u] = tim++;
for (int x : g[u]) {
assert(0 <= x && x < n);
if (x == u) {
continue;
}
if (x == fa) {
fa = n;
continue;
}
if (vis[x]) {
if (in[x] < in[u]) {
deg[u]++;
low[u] = std::min(low[u], in[x]);
} else {
deg[u]--;
int ch = pth[u];
while (ch != n && in[ch] <= in[x] && in[x] < out[ch]) {
abs(u, ch);
ch = pth[ch];
}
pth[u] = ch;
}
continue;
}
self(self, x, u);
if (pth[x] == n && deg[x] <= 1) {
deg[u] += deg[x];
low[u] = std::min(low[u], low[x]);
continue;
}
if (deg[x] == 0) {
x = pth[x];
}
if (low[x] < low[u]) {
low[u] = low[x];
std::swap(x, pth[u]);
}
while (x != n) {
abs(u, x);
x = pth[x];
}
}
out[u] = tim;
};
for (int u = 0; u < n; u++) {
if (!vis[u]) {
dfs(dfs, u, n);
}
}
return dsu.groups();
}
} // namespace noya
// NOYA_THREE_EDGE_CONNECTED_COMPONENTS_HPP