Strongly connected components
Grouping the vertices of a directed graph into components where everyone reaches everyone, with two DFS passes, in . 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)
- DFS over the whole graph, recording vertices in the order in which they finish.
- 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 between different components, . The test checks this too.
Both DFS passes here are iterative, with their own stack. Recursion of depth overflows the stack on many judges.
2-SAT
In Giant Pizza each requirement " or " becomes two implications, and , in a graph with 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 true if .
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 = 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.
// 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.
- Flight Routes Check · Graph Algorithms
- Planets and Kingdoms · Graph Algorithms
- Giant Pizza · Graph Algorithms
More in the USACO Guide
- Strongly Connected Components · usaco.guide/adv/SCC
In English, with more problems per level.