Strongly Connected Components (graph/scc.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-09-18 22:02:23+07:00
• Include: #include "graph/scc.hpp"

Description

Finds strongly connected components (SCCs) in a directed graph using Tarjan’s algorithm. The algorithm runs in $\mathcal O(V + E)$ time.

Functions

• find_scc(const G &g)
  • Returns a vector of vectors, where each inner vector contains the vertices in one SCC
  • SCCs are returned in topological order
  • Time complexity: $\mathcal O(V + E)$
• condense(const G &g)
  • Returns a tuple (scc, rep, gd) where:
    • scc: vector of SCCs (same as find_scc)
    • rep: mapping from vertex to its SCC index
    • gd: condensed DAG where each node represents an SCC
  • Time complexity: $\mathcal O(V + E)$ or $\mathcal O(V + E \log E)$ if you erase duplicated edges

Required by

• 2-SAT (other/two_sat.hpp)

Verified with

• test/yosupo/graph/scc_ael.test.cpp
• test/yosupo/graph/scc_csr.test.cpp
• test/yosupo/other/two_sat.test.cpp

Code

#pragma once

template<class G> auto find_scc(const G &g) {
    int n = (int)g.size();
    vector<int> val(n), z;
    vector<char> added(n);
    vector<basic_string<int>> scc;
    int time = 0;
    auto dfs = [&](auto &self, int v) -> int {
        int low = val[v] = time++;
        z.push_back(v);
        for (auto u : g[v])
            if (!added[u]) low = min(low, val[u] ?: self(self, u));
        if (low == val[v]) {
            scc.emplace_back();
            int x;
            do {
                x = z.back(), z.pop_back();
                added[x] = true;
                scc.back().push_back(x);
            } while (x != v);
        }
        return val[v] = low;
    };
    for (int i = 0; i < n; i++)
        if (!added[i]) dfs(dfs, i);
    reverse(begin(scc), end(scc));
    return scc;
}
template<class G> auto condense(const G &g) {
    auto scc = find_scc(g);
    int n = (int)scc.size();
    vector<int> rep(g.size());
    for (int i = 0; i < n; i++)
        for (auto v : scc[i]) rep[v] = i;
    vector<basic_string<int>> gd(n);
    for (int v = 0; v < g.size(); v++)
        for (auto u : g[v])
            if (rep[v] != rep[u]) gd[rep[v]].push_back(rep[u]);
    for (auto &v : gd) {
        sort(begin(v), end(v));
        v.erase(unique(begin(v), end(v)), end(v));
    }
    return make_tuple(move(scc), move(rep), move(gd));
}

#line 2 "graph/scc.hpp"

template<class G> auto find_scc(const G &g) {
    int n = (int)g.size();
    vector<int> val(n), z;
    vector<char> added(n);
    vector<basic_string<int>> scc;
    int time = 0;
    auto dfs = [&](auto &self, int v) -> int {
        int low = val[v] = time++;
        z.push_back(v);
        for (auto u : g[v])
            if (!added[u]) low = min(low, val[u] ?: self(self, u));
        if (low == val[v]) {
            scc.emplace_back();
            int x;
            do {
                x = z.back(), z.pop_back();
                added[x] = true;
                scc.back().push_back(x);
            } while (x != v);
        }
        return val[v] = low;
    };
    for (int i = 0; i < n; i++)
        if (!added[i]) dfs(dfs, i);
    reverse(begin(scc), end(scc));
    return scc;
}
template<class G> auto condense(const G &g) {
    auto scc = find_scc(g);
    int n = (int)scc.size();
    vector<int> rep(g.size());
    for (int i = 0; i < n; i++)
        for (auto v : scc[i]) rep[v] = i;
    vector<basic_string<int>> gd(n);
    for (int v = 0; v < g.size(); v++)
        for (auto u : g[v])
            if (rep[v] != rep[u]) gd[rep[v]].push_back(rep[u]);
    for (auto &v : gd) {
        sort(begin(v), end(v));
        v.erase(unique(begin(v), end(v)), end(v));
    }
    return make_tuple(move(scc), move(rep), move(gd));
}

Back to top page