Incremental Strongly Connected Components
(graph/incremental_scc.hpp)
- View this file on GitHub
- Last update: 2026-08-13 01:41:40+09:00
- Include:
#include "graph/incremental_scc.hpp"
Overview
incremental_scc(graph) processes a known sequence of directed edge
insertions offline. Edge IDs are their insertion positions.
For an edge with ID e, the returned value merge_time[e] is the smallest
time t satisfying e < t <= M such that its endpoints belong to the same SCC
after inserting all active edges with IDs less than t. The value M + 1
means this never happens.
These times describe every SCC merge. Starting with a DSU of singleton
vertices, at each time t, merge the endpoints of all edges satisfying
merge_time[e] == t. The resulting DSU groups are exactly the SCCs after the
first t insertion positions.
Graph Requirements
Build the graph with Graph<T>::add_directed_edge. Parallel edges and
self-loops are supported. Inactive edges are treated as no-op insertion
positions and receive merge time M + 1.
The SCC traversals are iterative; only the divide-and-conquer recursion remains,
and its depth is O(log(M + 1)). The function does not mutate the graph.
API
template <class T>
std::vector<int> incremental_scc(const Graph<T>& graph);
| Function | Description | Complexity |
|---|---|---|
incremental_scc(graph) |
Returns the first same-SCC time for every edge ID. |
O((N + M) log(M + 1)) time and O(N + M) auxiliary memory |
Example
#include "graph/graph.hpp"
#include "graph/incremental_scc.hpp"
#include <iostream>
int main() {
m1une::graph::Graph<> graph(3);
graph.add_directed_edge(0, 1);
graph.add_directed_edge(1, 2);
graph.add_directed_edge(2, 0);
auto merge_time = m1une::graph::incremental_scc(graph);
for (int time : merge_time) {
std::cout << time << "\n"; // all three values are 3
}
}
Depends on
Required by
Verified with
- verify/graph/cow_game.test.cpp
- verify/graph/graph_algorithms.test.cpp
- verify/graph/incremental_scc.test.cpp
- verify/graph/range_edge_graph.test.cpp
Code
#ifndef M1UNE_GRAPH_INCREMENTAL_SCC_HPP
#define M1UNE_GRAPH_INCREMENTAL_SCC_HPP 1
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
#include "graph.hpp"
namespace m1une {
namespace graph {
namespace incremental_scc_detail {
struct EdgeEvent {
int id;
int from;
int to;
};
inline std::vector<int> component_ids(
int vertex_count,
const std::vector<EdgeEvent>& edges,
int time
) {
std::vector<int> begin(vertex_count + 1, 0);
std::vector<int> reverse_begin(vertex_count + 1, 0);
int edge_count = 0;
for (const EdgeEvent& edge : edges) {
if (edge.id >= time) continue;
begin[edge.from + 1]++;
reverse_begin[edge.to + 1]++;
edge_count++;
}
for (int vertex = 0; vertex < vertex_count; vertex++) {
begin[vertex + 1] += begin[vertex];
reverse_begin[vertex + 1] += reverse_begin[vertex];
}
std::vector<int> adjacency(edge_count);
std::vector<int> reverse_adjacency(edge_count);
std::vector<int> cursor = begin;
std::vector<int> reverse_cursor = reverse_begin;
for (const EdgeEvent& edge : edges) {
if (edge.id >= time) continue;
adjacency[cursor[edge.from]++] = edge.to;
reverse_adjacency[reverse_cursor[edge.to]++] = edge.from;
}
std::vector<int>().swap(cursor);
std::vector<int>().swap(reverse_cursor);
std::vector<char> visited(vertex_count, false);
std::vector<int> next_position(begin.begin(), begin.end() - 1);
std::vector<int> order;
order.reserve(vertex_count);
std::vector<int> stack;
for (int start = 0; start < vertex_count; start++) {
if (visited[start]) continue;
visited[start] = true;
stack.push_back(start);
while (!stack.empty()) {
const int vertex = stack.back();
int& position = next_position[vertex];
if (position < begin[vertex + 1]) {
const int to = adjacency[position++];
if (!visited[to]) {
visited[to] = true;
stack.push_back(to);
}
} else {
order.push_back(vertex);
stack.pop_back();
}
}
}
std::vector<int> component(vertex_count, -1);
int component_count = 0;
for (auto iterator = order.rbegin(); iterator != order.rend(); ++iterator) {
const int start = *iterator;
if (component[start] != -1) continue;
component[start] = component_count;
stack.push_back(start);
while (!stack.empty()) {
const int vertex = stack.back();
stack.pop_back();
for (int position = reverse_begin[vertex];
position < reverse_begin[vertex + 1]; position++) {
const int to = reverse_adjacency[position];
if (component[to] != -1) continue;
component[to] = component_count;
stack.push_back(to);
}
}
component_count++;
}
return component;
}
} // namespace incremental_scc_detail
// For every directed edge e, returns the first time t after e is inserted such
// that its endpoints are in the same SCC. At time t, edges with IDs less than
// t have been inserted. edge_count() + 1 means this never happens.
template <class T>
std::vector<int> incremental_scc(const Graph<T>& graph) {
using incremental_scc_detail::EdgeEvent;
using incremental_scc_detail::component_ids;
const int vertex_count = graph.size();
const int edge_count = graph.edge_count();
const int never = edge_count + 1;
std::vector<int> merge_time(edge_count, never);
if (edge_count == 0) return merge_time;
std::vector<EdgeEvent> edges_by_id(edge_count);
std::vector<char> initialized(edge_count, false);
for (int vertex = 0; vertex < vertex_count; vertex++) {
for (const Edge<T>& edge : graph[vertex]) {
assert(0 <= edge.id && edge.id < edge_count);
assert(!initialized[edge.id]);
if (initialized[edge.id]) continue;
initialized[edge.id] = true;
edges_by_id[edge.id] = EdgeEvent{edge.id, edge.from, edge.to};
}
}
std::vector<EdgeEvent> events;
events.reserve(edge_count);
for (int edge_id = 0; edge_id < edge_count; edge_id++) {
assert(initialized[edge_id]);
if (graph.is_edge_alive(edge_id)) {
events.push_back(edges_by_id[edge_id]);
}
}
std::vector<EdgeEvent>().swap(edges_by_id);
std::vector<char>().swap(initialized);
std::vector<int> new_index(vertex_count, -1);
auto divide = [&](
auto&& self,
std::vector<EdgeEvent> current,
int left,
int right
) -> void {
if (current.empty() || right == left + 1) return;
const int middle = left + (right - left) / 2;
std::vector<int> touched;
touched.reserve(std::min(
std::size_t(vertex_count),
current.size() * 2
));
int compressed_count = 0;
for (const EdgeEvent& edge : current) {
if (new_index[edge.from] == -1) {
new_index[edge.from] = compressed_count++;
touched.push_back(edge.from);
}
if (new_index[edge.to] == -1) {
new_index[edge.to] = compressed_count++;
touched.push_back(edge.to);
}
}
for (EdgeEvent& edge : current) {
edge.from = new_index[edge.from];
edge.to = new_index[edge.to];
}
for (int vertex : touched) new_index[vertex] = -1;
std::vector<EdgeEvent> earlier;
std::vector<EdgeEvent> later;
earlier.reserve(current.size() / 2);
later.reserve(current.size() / 2);
{
std::vector<int> component =
component_ids(compressed_count, current, middle);
for (const EdgeEvent& edge : current) {
const int from_component = component[edge.from];
const int to_component = component[edge.to];
if (edge.id < middle &&
from_component == to_component) {
merge_time[edge.id] =
std::min(merge_time[edge.id], middle);
earlier.push_back(edge);
} else {
later.push_back(EdgeEvent{
edge.id,
from_component,
to_component
});
}
}
}
std::vector<EdgeEvent>().swap(current);
self(self, std::move(earlier), left, middle);
self(self, std::move(later), middle, right);
};
divide(divide, std::move(events), 0, edge_count + 1);
return merge_time;
}
} // namespace graph
} // namespace m1une
#endif // M1UNE_GRAPH_INCREMENTAL_SCC_HPP#line 1 "graph/incremental_scc.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#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/incremental_scc.hpp"
namespace m1une {
namespace graph {
namespace incremental_scc_detail {
struct EdgeEvent {
int id;
int from;
int to;
};
inline std::vector<int> component_ids(
int vertex_count,
const std::vector<EdgeEvent>& edges,
int time
) {
std::vector<int> begin(vertex_count + 1, 0);
std::vector<int> reverse_begin(vertex_count + 1, 0);
int edge_count = 0;
for (const EdgeEvent& edge : edges) {
if (edge.id >= time) continue;
begin[edge.from + 1]++;
reverse_begin[edge.to + 1]++;
edge_count++;
}
for (int vertex = 0; vertex < vertex_count; vertex++) {
begin[vertex + 1] += begin[vertex];
reverse_begin[vertex + 1] += reverse_begin[vertex];
}
std::vector<int> adjacency(edge_count);
std::vector<int> reverse_adjacency(edge_count);
std::vector<int> cursor = begin;
std::vector<int> reverse_cursor = reverse_begin;
for (const EdgeEvent& edge : edges) {
if (edge.id >= time) continue;
adjacency[cursor[edge.from]++] = edge.to;
reverse_adjacency[reverse_cursor[edge.to]++] = edge.from;
}
std::vector<int>().swap(cursor);
std::vector<int>().swap(reverse_cursor);
std::vector<char> visited(vertex_count, false);
std::vector<int> next_position(begin.begin(), begin.end() - 1);
std::vector<int> order;
order.reserve(vertex_count);
std::vector<int> stack;
for (int start = 0; start < vertex_count; start++) {
if (visited[start]) continue;
visited[start] = true;
stack.push_back(start);
while (!stack.empty()) {
const int vertex = stack.back();
int& position = next_position[vertex];
if (position < begin[vertex + 1]) {
const int to = adjacency[position++];
if (!visited[to]) {
visited[to] = true;
stack.push_back(to);
}
} else {
order.push_back(vertex);
stack.pop_back();
}
}
}
std::vector<int> component(vertex_count, -1);
int component_count = 0;
for (auto iterator = order.rbegin(); iterator != order.rend(); ++iterator) {
const int start = *iterator;
if (component[start] != -1) continue;
component[start] = component_count;
stack.push_back(start);
while (!stack.empty()) {
const int vertex = stack.back();
stack.pop_back();
for (int position = reverse_begin[vertex];
position < reverse_begin[vertex + 1]; position++) {
const int to = reverse_adjacency[position];
if (component[to] != -1) continue;
component[to] = component_count;
stack.push_back(to);
}
}
component_count++;
}
return component;
}
} // namespace incremental_scc_detail
// For every directed edge e, returns the first time t after e is inserted such
// that its endpoints are in the same SCC. At time t, edges with IDs less than
// t have been inserted. edge_count() + 1 means this never happens.
template <class T>
std::vector<int> incremental_scc(const Graph<T>& graph) {
using incremental_scc_detail::EdgeEvent;
using incremental_scc_detail::component_ids;
const int vertex_count = graph.size();
const int edge_count = graph.edge_count();
const int never = edge_count + 1;
std::vector<int> merge_time(edge_count, never);
if (edge_count == 0) return merge_time;
std::vector<EdgeEvent> edges_by_id(edge_count);
std::vector<char> initialized(edge_count, false);
for (int vertex = 0; vertex < vertex_count; vertex++) {
for (const Edge<T>& edge : graph[vertex]) {
assert(0 <= edge.id && edge.id < edge_count);
assert(!initialized[edge.id]);
if (initialized[edge.id]) continue;
initialized[edge.id] = true;
edges_by_id[edge.id] = EdgeEvent{edge.id, edge.from, edge.to};
}
}
std::vector<EdgeEvent> events;
events.reserve(edge_count);
for (int edge_id = 0; edge_id < edge_count; edge_id++) {
assert(initialized[edge_id]);
if (graph.is_edge_alive(edge_id)) {
events.push_back(edges_by_id[edge_id]);
}
}
std::vector<EdgeEvent>().swap(edges_by_id);
std::vector<char>().swap(initialized);
std::vector<int> new_index(vertex_count, -1);
auto divide = [&](
auto&& self,
std::vector<EdgeEvent> current,
int left,
int right
) -> void {
if (current.empty() || right == left + 1) return;
const int middle = left + (right - left) / 2;
std::vector<int> touched;
touched.reserve(std::min(
std::size_t(vertex_count),
current.size() * 2
));
int compressed_count = 0;
for (const EdgeEvent& edge : current) {
if (new_index[edge.from] == -1) {
new_index[edge.from] = compressed_count++;
touched.push_back(edge.from);
}
if (new_index[edge.to] == -1) {
new_index[edge.to] = compressed_count++;
touched.push_back(edge.to);
}
}
for (EdgeEvent& edge : current) {
edge.from = new_index[edge.from];
edge.to = new_index[edge.to];
}
for (int vertex : touched) new_index[vertex] = -1;
std::vector<EdgeEvent> earlier;
std::vector<EdgeEvent> later;
earlier.reserve(current.size() / 2);
later.reserve(current.size() / 2);
{
std::vector<int> component =
component_ids(compressed_count, current, middle);
for (const EdgeEvent& edge : current) {
const int from_component = component[edge.from];
const int to_component = component[edge.to];
if (edge.id < middle &&
from_component == to_component) {
merge_time[edge.id] =
std::min(merge_time[edge.id], middle);
earlier.push_back(edge);
} else {
later.push_back(EdgeEvent{
edge.id,
from_component,
to_component
});
}
}
}
std::vector<EdgeEvent>().swap(current);
self(self, std::move(earlier), left, middle);
self(self, std::move(later), middle, right);
};
divide(divide, std::move(events), 0, edge_count + 1);
return merge_time;
}
} // namespace graph
} // namespace m1une