uniolympiads Ελληνικά

Strongly connected components

Grouping the vertices of a directed graph into components where everyone reaches everyone, with two DFS passes, in O(n+m)O(n + m). 2-SAT follows from it.

When

"Can every city reach every other?", "split the planets into kingdoms", and every problem where a cycle in a directed graph can be contracted to one vertex. The graph of components (the condensation) is always a DAG.

The idea (Kosaraju)

  1. DFS over the whole graph, recording vertices in the order in which they finish.
  2. Reverse every edge. Take the vertices from the one that finished last backwards. Each DFS on the reversed graph from a vertex with no component yields exactly one component.

Why it works: the vertex that finishes last belongs to a "source" of the condensation. In the reversed graph that component becomes a "sink", so the DFS cannot leave it.

So the components come out in topological order of the condensation: for every edge u→vu \to v between different components, comp(u)<comp(v)\mathrm{comp}(u) < \mathrm{comp}(v). The test checks this too.

Both DFS passes here are iterative, with their own stack. Recursion of depth 2⋅1052 \cdot 10^5 overflows the stack on many judges.

2-SAT

In Giant Pizza each requirement "xx or yy" becomes two implications, ¬x→y\lnot x \to y and ¬y→x\lnot y \to x, in a graph with 2m2m vertices (each variable and its negation). A solution exists if and only if no variable is in the same component as its negation. Then set xx true if comp(x)>comp(¬x)\mathrm{comp}(x) > \mathrm{comp}(\lnot x).

Pitfalls

  • Finishing order is not visiting order. A vertex joins the list once all of its neighbours have been examined.
  • In 2-SAT the comparison of components depends on the direction of the numbering. With the code on this page (smaller comp\mathrm{comp} = earlier in topological order) it is >>, as written above.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/scc.cpp
// Strongly connected components, Kosaraju. O(n + m).
// comp[v] = index of v's component; components come out in topological order of the condensation
// (an edge u -> v between different components always has comp[u] < comp[v]).
// Both passes are iterative, so deep graphs (n = 2e5 on a path) do not overflow the stack.

struct SCC {
    int n;
    int count = 0;
    vector<int> comp;

    SCC(const vector<vector<int>>& adj) : n(adj.size()), comp(adj.size(), -1) {
        vector<vector<int>> radj(n);
        for (int u = 0; u < n; u++) {
            for (int v : adj[u]) {
                radj[v].push_back(u);
            }
        }
        // Pass 1: vertices in increasing finish time.
        vector<int> order;
        vector<char> seen(n, 0);
        vector<int> it(n, 0);
        for (int s = 0; s < n; s++) {
            if (seen[s]) {
                continue;
            }
            vector<int> stk = {s};
            seen[s] = 1;
            while (!stk.empty()) {
                int u = stk.back();
                if (it[u] < (int)adj[u].size()) {
                    int v = adj[u][it[u]];
                    it[u]++;
                    if (!seen[v]) {
                        seen[v] = 1;
                        stk.push_back(v);
                    }
                } else {
                    order.push_back(u);
                    stk.pop_back();
                }
            }
        }
        // Pass 2: on the reversed graph, latest finish first.
        for (int i = n - 1; i >= 0; i--) {
            int s = order[i];
            if (comp[s] != -1) {
                continue;
            }
            vector<int> stk = {s};
            comp[s] = count;
            while (!stk.empty()) {
                int u = stk.back();
                stk.pop_back();
                for (int v : radj[u]) {
                    if (comp[v] == -1) {
                        comp[v] = count;
                        stk.push_back(v);
                    }
                }
            }
            count++;
        }
    }
};

Tested on 1,501 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.