Three-Edge-Connected Components
(graph/three_edge_connected_components.hpp)
- View this file on GitHub
- Last update: 2026-08-13 01:41:40+09:00
- Include:
#include "graph/three_edge_connected_components.hpp"
Overview
Two vertices are three-edge-connected when at least three edge-disjoint paths join them. Equivalently, deleting any two edges cannot separate them.
three_edge_connected_components partitions the vertices into the maximal sets
defined by this relation. It uses the linear-time one-pass contraction algorithm
of Tsin.
Graph Requirements
Build the undirected graph with Graph<T>::add_edge. Directed edges are not
supported. The graph may be disconnected.
Parallel edges are distinct and therefore contribute separately to edge connectivity. Self-loops do not join different vertices and are ignored. Inactive edges are also ignored.
The DFS is iterative, so a path or cycle with many vertices does not consume the call stack.
API
struct ThreeEdgeConnectedComponentsResult {
std::vector<std::vector<int>> components;
std::vector<int> component_of_vertex;
int component_count() const;
bool same(int first, int second) const;
};
template <class T>
ThreeEdgeConnectedComponentsResult three_edge_connected_components(
const Graph<T>& graph
);
| Member or function | Description | Complexity |
|---|---|---|
components[c] |
Vertices in component c; their order is unspecified. |
– |
component_of_vertex[v] |
Component containing vertex v. |
$O(1)$ |
component_count() |
Number of three-edge-connected components. | $O(1)$ |
same(u, v) |
Whether u and v are three-edge-connected. |
$O(1)$ |
three_edge_connected_components(graph) |
Computes the complete decomposition. | $O(N+M)$ |
The function uses $O(N+M)$ memory including the input graph and does not mutate the graph.
Example
#include "graph/graph.hpp"
#include "graph/three_edge_connected_components.hpp"
#include <iostream>
int main() {
m1une::graph::Graph<> graph(3);
graph.add_edge(0, 1);
graph.add_edge(0, 1);
graph.add_edge(0, 1);
graph.add_edge(1, 2);
auto result = m1une::graph::three_edge_connected_components(graph);
std::cout << result.same(0, 1) << "\n"; // 1
std::cout << result.same(1, 2) << "\n"; // 0
}
Depends on
Required by
Verified with
- verify/graph/cow_game.test.cpp
- verify/graph/graph_algorithms.test.cpp
- verify/graph/range_edge_graph.test.cpp
- verify/graph/three_edge_connected_components.test.cpp
Code
#ifndef M1UNE_GRAPH_THREE_EDGE_CONNECTED_COMPONENTS_HPP
#define M1UNE_GRAPH_THREE_EDGE_CONNECTED_COMPONENTS_HPP 1
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>
#include "graph.hpp"
namespace m1une {
namespace graph {
struct ThreeEdgeConnectedComponentsResult {
std::vector<std::vector<int>> components;
std::vector<int> component_of_vertex;
int component_count() const {
return int(components.size());
}
bool same(int first, int second) const {
assert(0 <= first && first < int(component_of_vertex.size()));
assert(0 <= second && second < int(component_of_vertex.size()));
return component_of_vertex[first] == component_of_vertex[second];
}
};
namespace internal {
// Maintains every component as a circular linked list. Swapping two successors
// concatenates two different lists in O(1) time.
struct ThreeEdgeComponentCycles {
std::vector<int> next;
explicit ThreeEdgeComponentCycles(int n) : next(n) {
std::iota(next.begin(), next.end(), 0);
}
void unite(int first, int second) {
std::swap(next[first], next[second]);
}
ThreeEdgeConnectedComponentsResult build_result() const {
const int n = int(next.size());
ThreeEdgeConnectedComponentsResult result;
result.component_of_vertex.assign(n, -1);
for (int first = 0; first < n; first++) {
if (result.component_of_vertex[first] != -1) continue;
const int component = result.component_count();
result.components.emplace_back();
int vertex = first;
do {
result.component_of_vertex[vertex] = component;
result.components.back().push_back(vertex);
vertex = next[vertex];
} while (vertex != first);
}
return result;
}
};
} // namespace internal
// Decomposes an undirected multigraph into maximal vertex sets joined by at
// least three edge-disjoint paths. This is an iterative form of Tsin's
// one-pass contraction algorithm.
template <class T>
ThreeEdgeConnectedComponentsResult three_edge_connected_components(
const Graph<T>& graph
) {
const int n = graph.size();
const int edge_count = graph.edge_count();
#ifndef NDEBUG
std::vector<int> incidence_count(edge_count, 0);
for (int vertex = 0; vertex < n; vertex++) {
for (const Edge<T>& edge : graph[vertex]) {
if (!edge.alive) continue;
assert(edge.from == vertex);
assert(0 <= edge.to && edge.to < n);
assert(0 <= edge.id && edge.id < edge_count);
incidence_count[edge.id]++;
}
}
for (int edge_id = 0; edge_id < edge_count; edge_id++) {
if (incidence_count[edge_id] != 0) assert(incidence_count[edge_id] == 2);
}
#endif
const int none = n;
std::vector<int> enter(n, -1);
std::vector<int> leave(n, 0);
std::vector<int> low(n, none);
std::vector<int> degree(n, 0);
std::vector<int> path(n, none);
std::vector<int> parent(n, -1);
std::vector<int> parent_edge(n, -1);
std::vector<int> next_edge(n, 0);
std::vector<int> dfs_stack;
internal::ThreeEdgeComponentCycles component_cycles(n);
int timer = 0;
auto absorb = [&](int vertex, int other) {
component_cycles.unite(vertex, other);
degree[vertex] += degree[other];
};
auto process_visited_edge = [&](int vertex, int to) {
if (enter[to] < enter[vertex]) {
degree[vertex]++;
low[vertex] = std::min(low[vertex], enter[to]);
return;
}
degree[vertex]--;
int current = path[vertex];
while (current != none && enter[current] <= enter[to] && enter[to] < leave[current]) {
absorb(vertex, current);
current = path[current];
}
path[vertex] = current;
};
auto process_child = [&](int vertex, int child) {
if (path[child] == none && degree[child] <= 1) {
degree[vertex] += degree[child];
low[vertex] = std::min(low[vertex], low[child]);
return;
}
int current = child;
if (degree[child] == 0) current = path[child];
assert(current != none);
if (low[current] < low[vertex]) {
low[vertex] = low[current];
std::swap(current, path[vertex]);
}
while (current != none) {
absorb(vertex, current);
current = path[current];
}
};
for (int root = 0; root < n; root++) {
if (enter[root] != -1) continue;
enter[root] = timer++;
dfs_stack.push_back(root);
while (!dfs_stack.empty()) {
const int vertex = dfs_stack.back();
if (next_edge[vertex] < int(graph[vertex].size())) {
const Edge<T>& edge = graph[vertex][next_edge[vertex]++];
if (!edge.alive || edge.from == edge.to || edge.id == parent_edge[vertex]) continue;
const int to = edge.to;
if (enter[to] == -1) {
parent[to] = vertex;
parent_edge[to] = edge.id;
enter[to] = timer++;
dfs_stack.push_back(to);
} else {
process_visited_edge(vertex, to);
}
continue;
}
leave[vertex] = timer;
dfs_stack.pop_back();
if (parent[vertex] != -1) process_child(parent[vertex], vertex);
}
}
return component_cycles.build_result();
}
} // namespace graph
} // namespace m1une
#endif // M1UNE_GRAPH_THREE_EDGE_CONNECTED_COMPONENTS_HPP#line 1 "graph/three_edge_connected_components.hpp"
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>
#line 1 "graph/graph.hpp"
#include <array>
#line 8 "graph/graph.hpp"
namespace m1une {
namespace graph {
template <class T = int>
struct Edge {
using cost_type = T;
int from;
int to;
T cost;
int id;
bool alive;
Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
: from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}
int other(int v) const {
assert(v == from || v == to);
return from ^ to ^ v;
}
};
template <class T = int>
struct Graph {
using edge_type = Edge<T>;
using cost_type = T;
private:
struct EdgePositions {
std::array<std::pair<int, int>, 2> value{};
int size = 0;
void push_back(std::pair<int, int> position) {
assert(size < 2);
value[size++] = position;
}
};
int _n;
int _edge_count;
std::vector<std::vector<edge_type>> _g;
std::vector<EdgePositions> _edge_positions;
public:
Graph() : _n(0), _edge_count(0) {}
explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
assert(0 <= n);
}
int size() const {
return _n;
}
bool empty() const {
return _n == 0;
}
int edge_count() const {
return _edge_count;
}
int add_vertex() {
_g.emplace_back();
return _n++;
}
int add_directed_edge(int from, int to, T cost = T(1)) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
int id = _edge_count++;
int idx = int(_g[from].size());
_g[from].push_back(edge_type(from, to, cost, id));
_edge_positions.emplace_back();
_edge_positions.back().push_back({from, idx});
return id;
}
int add_edge(int u, int v, T cost = T(1)) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
int id = _edge_count++;
int u_idx = int(_g[u].size());
_g[u].push_back(edge_type(u, v, cost, id));
int v_idx = int(_g[v].size());
_g[v].push_back(edge_type(v, u, cost, id));
_edge_positions.emplace_back();
_edge_positions.back().push_back({u, u_idx});
_edge_positions.back().push_back({v, v_idx});
return id;
}
void set_edge_alive(int id, bool alive) {
assert(0 <= id && id < _edge_count);
for (int i = 0; i < _edge_positions[id].size; ++i) {
auto [v, idx] = _edge_positions[id].value[i];
_g[v][idx].alive = alive;
}
}
void erase_edge(int id) {
set_edge_alive(id, false);
}
void revive_edge(int id) {
set_edge_alive(id, true);
}
bool is_edge_alive(int id) const {
assert(0 <= id && id < _edge_count);
assert(_edge_positions[id].size != 0);
auto [v, idx] = _edge_positions[id].value[0];
return _g[v][idx].alive;
}
const std::vector<edge_type>& operator[](int v) const {
assert(0 <= v && v < _n);
return _g[v];
}
std::vector<edge_type>& operator[](int v) {
assert(0 <= v && v < _n);
return _g[v];
}
const std::vector<std::vector<edge_type>>& adjacency() const {
return _g;
}
std::vector<std::vector<edge_type>>& adjacency() {
return _g;
}
std::vector<edge_type> edges(bool include_inactive = false) const {
std::vector<edge_type> result;
result.reserve(_edge_count);
std::vector<char> used(_edge_count, false);
for (int v = 0; v < _n; v++) {
for (const auto& e : _g[v]) {
if (!include_inactive && !e.alive) continue;
if (0 <= e.id && e.id < _edge_count) {
if (used[e.id]) continue;
used[e.id] = true;
}
result.push_back(e);
}
}
return result;
}
Graph reversed() const {
Graph result(_n);
result._edge_count = _edge_count;
result._edge_positions.assign(_edge_count, {});
for (int v = 0; v < _n; v++) {
for (const auto& e : _g[v]) {
int idx = int(result._g[e.to].size());
result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
}
}
return result;
}
};
} // namespace graph
} // namespace m1une
#line 11 "graph/three_edge_connected_components.hpp"
namespace m1une {
namespace graph {
struct ThreeEdgeConnectedComponentsResult {
std::vector<std::vector<int>> components;
std::vector<int> component_of_vertex;
int component_count() const {
return int(components.size());
}
bool same(int first, int second) const {
assert(0 <= first && first < int(component_of_vertex.size()));
assert(0 <= second && second < int(component_of_vertex.size()));
return component_of_vertex[first] == component_of_vertex[second];
}
};
namespace internal {
// Maintains every component as a circular linked list. Swapping two successors
// concatenates two different lists in O(1) time.
struct ThreeEdgeComponentCycles {
std::vector<int> next;
explicit ThreeEdgeComponentCycles(int n) : next(n) {
std::iota(next.begin(), next.end(), 0);
}
void unite(int first, int second) {
std::swap(next[first], next[second]);
}
ThreeEdgeConnectedComponentsResult build_result() const {
const int n = int(next.size());
ThreeEdgeConnectedComponentsResult result;
result.component_of_vertex.assign(n, -1);
for (int first = 0; first < n; first++) {
if (result.component_of_vertex[first] != -1) continue;
const int component = result.component_count();
result.components.emplace_back();
int vertex = first;
do {
result.component_of_vertex[vertex] = component;
result.components.back().push_back(vertex);
vertex = next[vertex];
} while (vertex != first);
}
return result;
}
};
} // namespace internal
// Decomposes an undirected multigraph into maximal vertex sets joined by at
// least three edge-disjoint paths. This is an iterative form of Tsin's
// one-pass contraction algorithm.
template <class T>
ThreeEdgeConnectedComponentsResult three_edge_connected_components(
const Graph<T>& graph
) {
const int n = graph.size();
const int edge_count = graph.edge_count();
#ifndef NDEBUG
std::vector<int> incidence_count(edge_count, 0);
for (int vertex = 0; vertex < n; vertex++) {
for (const Edge<T>& edge : graph[vertex]) {
if (!edge.alive) continue;
assert(edge.from == vertex);
assert(0 <= edge.to && edge.to < n);
assert(0 <= edge.id && edge.id < edge_count);
incidence_count[edge.id]++;
}
}
for (int edge_id = 0; edge_id < edge_count; edge_id++) {
if (incidence_count[edge_id] != 0) assert(incidence_count[edge_id] == 2);
}
#endif
const int none = n;
std::vector<int> enter(n, -1);
std::vector<int> leave(n, 0);
std::vector<int> low(n, none);
std::vector<int> degree(n, 0);
std::vector<int> path(n, none);
std::vector<int> parent(n, -1);
std::vector<int> parent_edge(n, -1);
std::vector<int> next_edge(n, 0);
std::vector<int> dfs_stack;
internal::ThreeEdgeComponentCycles component_cycles(n);
int timer = 0;
auto absorb = [&](int vertex, int other) {
component_cycles.unite(vertex, other);
degree[vertex] += degree[other];
};
auto process_visited_edge = [&](int vertex, int to) {
if (enter[to] < enter[vertex]) {
degree[vertex]++;
low[vertex] = std::min(low[vertex], enter[to]);
return;
}
degree[vertex]--;
int current = path[vertex];
while (current != none && enter[current] <= enter[to] && enter[to] < leave[current]) {
absorb(vertex, current);
current = path[current];
}
path[vertex] = current;
};
auto process_child = [&](int vertex, int child) {
if (path[child] == none && degree[child] <= 1) {
degree[vertex] += degree[child];
low[vertex] = std::min(low[vertex], low[child]);
return;
}
int current = child;
if (degree[child] == 0) current = path[child];
assert(current != none);
if (low[current] < low[vertex]) {
low[vertex] = low[current];
std::swap(current, path[vertex]);
}
while (current != none) {
absorb(vertex, current);
current = path[current];
}
};
for (int root = 0; root < n; root++) {
if (enter[root] != -1) continue;
enter[root] = timer++;
dfs_stack.push_back(root);
while (!dfs_stack.empty()) {
const int vertex = dfs_stack.back();
if (next_edge[vertex] < int(graph[vertex].size())) {
const Edge<T>& edge = graph[vertex][next_edge[vertex]++];
if (!edge.alive || edge.from == edge.to || edge.id == parent_edge[vertex]) continue;
const int to = edge.to;
if (enter[to] == -1) {
parent[to] = vertex;
parent_edge[to] = edge.id;
enter[to] = timer++;
dfs_stack.push_back(to);
} else {
process_visited_edge(vertex, to);
}
continue;
}
leave[vertex] = timer;
dfs_stack.pop_back();
if (parent[vertex] != -1) process_child(parent[vertex], vertex);
}
}
return component_cycles.build_result();
}
} // namespace graph
} // namespace m1une