three_edge_connected_components.hpp¶
把无向图分解为三边连通分量；用于分析删除任意两条边后的连通结构。
Complexity: Time: O(n + m). Space: O(n + m).
AC 记录：three_edge_connected_components。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n + m).
/// Space: O(n + m).
#include <algorithm>
#include <cassert>
#include <functional>
#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 any 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.
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;
int n = int(g.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];
};
std::function<void(int, int)> dfs = [&](int u, int fa) {
vis[u] = true;
in[u] = tim++;
for (int x : g[u]) {
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;
}
dfs(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(u, n);
}
}
return dsu.groups();
}
} // namespace noya
#ifndef NOYA_THREE_EDGE_CONNECTED_COMPONENTS_HPP
#define NOYA_THREE_EDGE_CONNECTED_COMPONENTS_HPP 1
/// @complexity Time: O(n + m).
/// Space: O(n + m).
#include <algorithm>
#include <cassert>
#include <functional>
#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 any 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.
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;
int n = int(g.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];
};
std::function<void(int, int)> dfs = [&](int u, int fa) {
vis[u] = true;
in[u] = tim++;
for (int x : g[u]) {
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;
}
dfs(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(u, n);
}
}
return dsu.groups();
}
} // namespace noya
#endif // NOYA_THREE_EDGE_CONNECTED_COMPONENTS_HPP
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <vector>
/// @complexity Time: O(n + m).
/// Space: O(n + m).
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 any 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.
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;
int n = int(g.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];
};
std::function<void(int, int)> dfs = [&](int u, int fa) {
vis[u] = true;
in[u] = tim++;
for (int x : g[u]) {
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;
}
dfs(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(u, n);
}
}
return dsu.groups();
}
} // namespace noya