three_edge_connected_components.hpp¶
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.
Verified by three_edge_connected_components.
把无向图分解为三边连通分量；用于分析删除任意两条边后的连通结构。
Implementation¶
#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> next_;
public:
explicit circular_partition(int size) : next_(size) {
std::iota(next_.begin(), next_.end(), 0);
}
void merge(int first, int second) {
assert(0 <= first && first < int(next_.size()));
assert(0 <= second && second < int(next_.size()));
std::swap(next_[first], next_[second]);
}
std::vector<std::vector<int>> groups() const {
std::vector<std::vector<int>> result;
std::vector<bool> visited(next_.size());
for (int start = 0; start < int(next_.size()); start++) {
if (visited[start]) {
continue;
}
result.emplace_back();
int vertex = start;
do {
visited[vertex] = true;
result.back().push_back(vertex);
vertex = next_[vertex];
} while (vertex != start);
}
return result;
}
};
} // 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>> &graph) {
using three_edge_connected_components_internal::circular_partition;
int vertex_count = int(graph.size());
std::vector<int> enter(vertex_count);
std::vector<int> leave(vertex_count);
std::vector<int> low(vertex_count, vertex_count);
std::vector<int> degree(vertex_count);
std::vector<int> path(vertex_count, vertex_count);
std::vector<bool> visited(vertex_count);
circular_partition components(vertex_count);
int timer = 0;
auto absorb = [&](int vertex, int child) {
components.merge(vertex, child);
degree[vertex] += degree[child];
};
std::function<void(int, int)> dfs = [&](int vertex, int parent) {
visited[vertex] = true;
enter[vertex] = timer++;
for (int neighbor : graph[vertex]) {
if (neighbor == vertex) {
continue;
}
if (neighbor == parent) {
parent = vertex_count;
continue;
}
if (visited[neighbor]) {
if (enter[neighbor] < enter[vertex]) {
degree[vertex]++;
low[vertex] = std::min(low[vertex], enter[neighbor]);
} else {
degree[vertex]--;
int chain = path[vertex];
while (chain != vertex_count && enter[chain] <= enter[neighbor] &&
enter[neighbor] < leave[chain]) {
absorb(vertex, chain);
chain = path[chain];
}
path[vertex] = chain;
}
continue;
}
dfs(neighbor, vertex);
if (path[neighbor] == vertex_count && degree[neighbor] <= 1) {
degree[vertex] += degree[neighbor];
low[vertex] = std::min(low[vertex], low[neighbor]);
continue;
}
if (degree[neighbor] == 0) {
neighbor = path[neighbor];
}
if (low[neighbor] < low[vertex]) {
low[vertex] = low[neighbor];
std::swap(neighbor, path[vertex]);
}
while (neighbor != vertex_count) {
absorb(vertex, neighbor);
neighbor = path[neighbor];
}
}
leave[vertex] = timer;
};
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (!visited[vertex]) {
dfs(vertex, vertex_count);
}
}
return components.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> next_;
public:
explicit circular_partition(int size) : next_(size) {
std::iota(next_.begin(), next_.end(), 0);
}
void merge(int first, int second) {
assert(0 <= first && first < int(next_.size()));
assert(0 <= second && second < int(next_.size()));
std::swap(next_[first], next_[second]);
}
std::vector<std::vector<int>> groups() const {
std::vector<std::vector<int>> result;
std::vector<bool> visited(next_.size());
for (int start = 0; start < int(next_.size()); start++) {
if (visited[start]) {
continue;
}
result.emplace_back();
int vertex = start;
do {
visited[vertex] = true;
result.back().push_back(vertex);
vertex = next_[vertex];
} while (vertex != start);
}
return result;
}
};
} // 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>> &graph) {
using three_edge_connected_components_internal::circular_partition;
int vertex_count = int(graph.size());
std::vector<int> enter(vertex_count);
std::vector<int> leave(vertex_count);
std::vector<int> low(vertex_count, vertex_count);
std::vector<int> degree(vertex_count);
std::vector<int> path(vertex_count, vertex_count);
std::vector<bool> visited(vertex_count);
circular_partition components(vertex_count);
int timer = 0;
auto absorb = [&](int vertex, int child) {
components.merge(vertex, child);
degree[vertex] += degree[child];
};
std::function<void(int, int)> dfs = [&](int vertex, int parent) {
visited[vertex] = true;
enter[vertex] = timer++;
for (int neighbor : graph[vertex]) {
if (neighbor == vertex) {
continue;
}
if (neighbor == parent) {
parent = vertex_count;
continue;
}
if (visited[neighbor]) {
if (enter[neighbor] < enter[vertex]) {
degree[vertex]++;
low[vertex] = std::min(low[vertex], enter[neighbor]);
} else {
degree[vertex]--;
int chain = path[vertex];
while (chain != vertex_count && enter[chain] <= enter[neighbor] &&
enter[neighbor] < leave[chain]) {
absorb(vertex, chain);
chain = path[chain];
}
path[vertex] = chain;
}
continue;
}
dfs(neighbor, vertex);
if (path[neighbor] == vertex_count && degree[neighbor] <= 1) {
degree[vertex] += degree[neighbor];
low[vertex] = std::min(low[vertex], low[neighbor]);
continue;
}
if (degree[neighbor] == 0) {
neighbor = path[neighbor];
}
if (low[neighbor] < low[vertex]) {
low[vertex] = low[neighbor];
std::swap(neighbor, path[vertex]);
}
while (neighbor != vertex_count) {
absorb(vertex, neighbor);
neighbor = path[neighbor];
}
}
leave[vertex] = timer;
};
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (!visited[vertex]) {
dfs(vertex, vertex_count);
}
}
return components.groups();
}
} // namespace noya