Strongly Connected Components
(graph/scc.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/scc.hpp"

Overview

A strongly connected component is a maximal set of vertices where every vertex can reach every other vertex in the same set. SCC decomposition compresses each such set into one component, turning any directed graph into a DAG of components.

Use SCC when you need to reason about mutual reachability, directed cycles, 2-SAT-style implications, or DP over the condensation graph.

This implementation is based on Tarjan’s DFS lowlink method and runs in linear time.

Graph Orientation

Directed only. SCCs are about mutual reachability through directed edges. For ordinary undirected components, use connected_components.

How to Use It

Build a directed graph with add_directed_edge, then call strongly_connected_components(g).

The result contains these members:

Member	Type / Signature	Meaning
`count`	`int`	Number of strongly connected components.
`comp`	`std::vector<int>`	`comp[v]` is the component id of vertex `v`.
`groups`	`std::vector<std::vector<int>>`	`groups[c]` is the list of vertices belonging to component `c`.
`same`	`bool same(int u, int v) const`	Returns whether `u` and `v` are in the same component.
`dag`	`template <class T> Graph<int> dag(const Graph<T>& g) const`	Builds the condensation DAG with duplicate component edges removed.

Component ids are arranged in topological order of the condensation DAG: edges between different components go from a smaller id to a larger id.

What `dag(g)` Represents

dag(g) returns the condensation graph of g. Its vertices are SCC ids, not original graph vertices.

Vertex c in the returned DAG represents groups[c], the c-th strongly connected component. In other words:

v belongs to DAG vertex c  <=>  comp[v] == c

For example, if groups[2] == {4, 6, 7}, then vertex 2 of the returned DAG represents original vertices 4, 6, and 7.

An SCC is not necessarily a single simple cycle. A DAG vertex may represent a single isolated original vertex, one directed cycle, or a larger mutually reachable subgraph containing several cycles.

If the original graph has an edge u -> v and comp[u] != comp[v], the returned DAG has an edge comp[u] -> comp[v]. Therefore each DAG edge means “there exists at least one original edge from some vertex in groups[from] to some vertex in groups[to]”.

Duplicate edges between the same pair of components are removed. The returned graph has type Graph<int> and its edge costs are all 1.

Functions

Function	Signature	Description	Complexity
`strongly_connected_components`	`template <class T> SccResult strongly_connected_components(const Graph<T>& g)`	Returns component ids and groups.	$O(N + M)$

Example

#include "graph/graph.hpp"
#include "graph/scc.hpp"
#include <iostream>

int main() {
    m1une::graph::Graph<> g(4);
    g.add_directed_edge(0, 1);
    g.add_directed_edge(1, 0);
    g.add_directed_edge(1, 2);
    g.add_directed_edge(2, 3);
    g.add_directed_edge(3, 2);

    auto scc = m1une::graph::strongly_connected_components(g);
    std::cout << scc.count << "\n";       // 2
    std::cout << scc.same(0, 1) << "\n";  // 1
    std::cout << scc.same(0, 2) << "\n";  // 0

    auto dag = scc.dag(g);
    std::cout << dag.size() << "\n";      // 2
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_SCC_HPP
#define M1UNE_GRAPH_SCC_HPP 1

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

struct SccResult {
    int count;
    std::vector<int> comp;
    std::vector<std::vector<int>> groups;

    bool same(int u, int v) const {
        assert(0 <= u && u < int(comp.size()));
        assert(0 <= v && v < int(comp.size()));
        return comp[u] == comp[v];
    }

    template <class T>
    Graph<int> dag(const Graph<T>& g) const {
        std::vector<std::pair<int, int>> edges;
        for (int v = 0; v < g.size(); v++) {
            for (const auto& e : g[v]) {
                if (!e.alive) continue;
                int a = comp[e.from], b = comp[e.to];
                if (a != b) edges.emplace_back(a, b);
            }
        }
        std::sort(edges.begin(), edges.end());
        edges.erase(std::unique(edges.begin(), edges.end()), edges.end());

        Graph<int> result(count);
        for (auto [a, b] : edges) result.add_directed_edge(a, b);
        return result;
    }
};

template <class T>
SccResult strongly_connected_components(const Graph<T>& g) {
    const int n = g.size();
    std::vector<std::vector<int>> reverse_graph(n);
    for (int vertex = 0; vertex < n; vertex++) {
        for (const auto& edge : g[vertex]) {
            if (edge.alive) reverse_graph[edge.to].push_back(vertex);
        }
    }

    std::vector<char> seen(n, false);
    std::vector<int> order;
    order.reserve(n);
    std::vector<std::pair<int, std::size_t>> dfs_stack;
    for (int start = 0; start < n; start++) {
        if (seen[start]) continue;
        seen[start] = true;
        dfs_stack.emplace_back(start, 0);
        while (!dfs_stack.empty()) {
            int vertex = dfs_stack.back().first;
            std::size_t& edge_index = dfs_stack.back().second;
            while (edge_index < g[vertex].size() &&
                   !g[vertex][edge_index].alive) {
                edge_index++;
            }
            if (edge_index == g[vertex].size()) {
                order.push_back(vertex);
                dfs_stack.pop_back();
                continue;
            }
            const int to = g[vertex][edge_index++].to;
            if (!seen[to]) {
                seen[to] = true;
                dfs_stack.emplace_back(to, 0);
            }
        }
    }

    std::vector<int> comp(n, -1);
    std::vector<std::vector<int>> groups;
    std::vector<int> stack;
    for (auto iterator = order.rbegin(); iterator != order.rend(); ++iterator) {
        const int start = *iterator;
        if (comp[start] != -1) continue;
        const int component = int(groups.size());
        groups.emplace_back();
        comp[start] = component;
        stack.push_back(start);
        while (!stack.empty()) {
            const int vertex = stack.back();
            stack.pop_back();
            groups.back().push_back(vertex);
            for (int to : reverse_graph[vertex]) {
                if (comp[to] != -1) continue;
                comp[to] = component;
                stack.push_back(to);
            }
        }
    }

    return SccResult{int(groups.size()), std::move(comp), std::move(groups)};
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_SCC_HPP

#line 1 "graph/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/scc.hpp"

namespace m1une {
namespace graph {

struct SccResult {
    int count;
    std::vector<int> comp;
    std::vector<std::vector<int>> groups;

    bool same(int u, int v) const {
        assert(0 <= u && u < int(comp.size()));
        assert(0 <= v && v < int(comp.size()));
        return comp[u] == comp[v];
    }

    template <class T>
    Graph<int> dag(const Graph<T>& g) const {
        std::vector<std::pair<int, int>> edges;
        for (int v = 0; v < g.size(); v++) {
            for (const auto& e : g[v]) {
                if (!e.alive) continue;
                int a = comp[e.from], b = comp[e.to];
                if (a != b) edges.emplace_back(a, b);
            }
        }
        std::sort(edges.begin(), edges.end());
        edges.erase(std::unique(edges.begin(), edges.end()), edges.end());

        Graph<int> result(count);
        for (auto [a, b] : edges) result.add_directed_edge(a, b);
        return result;
    }
};

template <class T>
SccResult strongly_connected_components(const Graph<T>& g) {
    const int n = g.size();
    std::vector<std::vector<int>> reverse_graph(n);
    for (int vertex = 0; vertex < n; vertex++) {
        for (const auto& edge : g[vertex]) {
            if (edge.alive) reverse_graph[edge.to].push_back(vertex);
        }
    }

    std::vector<char> seen(n, false);
    std::vector<int> order;
    order.reserve(n);
    std::vector<std::pair<int, std::size_t>> dfs_stack;
    for (int start = 0; start < n; start++) {
        if (seen[start]) continue;
        seen[start] = true;
        dfs_stack.emplace_back(start, 0);
        while (!dfs_stack.empty()) {
            int vertex = dfs_stack.back().first;
            std::size_t& edge_index = dfs_stack.back().second;
            while (edge_index < g[vertex].size() &&
                   !g[vertex][edge_index].alive) {
                edge_index++;
            }
            if (edge_index == g[vertex].size()) {
                order.push_back(vertex);
                dfs_stack.pop_back();
                continue;
            }
            const int to = g[vertex][edge_index++].to;
            if (!seen[to]) {
                seen[to] = true;
                dfs_stack.emplace_back(to, 0);
            }
        }
    }

    std::vector<int> comp(n, -1);
    std::vector<std::vector<int>> groups;
    std::vector<int> stack;
    for (auto iterator = order.rbegin(); iterator != order.rend(); ++iterator) {
        const int start = *iterator;
        if (comp[start] != -1) continue;
        const int component = int(groups.size());
        groups.emplace_back();
        comp[start] = component;
        stack.push_back(start);
        while (!stack.empty()) {
            const int vertex = stack.back();
            stack.pop_back();
            groups.back().push_back(vertex);
            for (int to : reverse_graph[vertex]) {
                if (comp[to] != -1) continue;
                comp[to] = component;
                stack.push_back(to);
            }
        }
    }

    return SccResult{int(groups.size()), std::move(comp), std::move(groups)};
}

}  // namespace graph
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Strongly Connected Components
(graph/scc.hpp)

Overview

Graph Orientation

How to Use It

What `dag(g)` Represents

Functions

Example

Depends on

Required by

Verified with

Code

Strongly Connected Components (graph/scc.hpp)

Overview

Graph Orientation

How to Use It

What dag(g) Represents

Functions

Example

Depends on

Required by

Verified with

Code

Strongly Connected Components
(graph/scc.hpp)

What `dag(g)` Represents