---
title: "Strongly Connected Components"
summary: Kosaraju and Tarjan in linear time, why the second pass needs the transpose, and the condensation as a working object.
difficulty: core
tags: [SCC, condensation, 2-SAT]
time: n + m
space: n + m
prereq: [trees/dfs, directed/definitions]
see: [special/twosat, flow/cuts, matching/applications]
---

:::definition label="SCC"
A **strongly connected component** is a maximal set $C \subseteq V$ such that every $u,v \in C$ satisfy $u \leadsto v$ and $v \leadsto u$. Maximality is what makes them a partition: if two vertex sets are mutually reachable into each other, they are one component.
:::

Condensing each component into a single vertex gives the **condensation** $G^{SCC}$ — always a DAG (@directed/definitions). The whole game is computing it in $O(n+m)$.

## Kosaraju: two DFS passes
1. DFS on $G$; record **finish times**.
2. DFS on $G^{\mathsf T}$ (transpose), visiting vertices in **decreasing** finish time; each DFS tree is one SCC.

```cpp kosaraju.cpp
int n; vector<vector<int>> g, gt; vector<char> used(n); vector<int> order, comp(n, -1);
void dfs1(int u) { used[u] = 1; for (int v : g[u]) if (!used[v]) dfs1(v); order.push_back(u); }
void dfs2(int u, int c) { comp[u] = c; for (int v : gt[u]) if (comp[v] == -1) dfs2(v, c); }

void scc() {
    for (int i = 0; i < n; i++) if (!used[i]) dfs1(i);          // pass 1 on G
    reverse(order.begin(), order.end());
    for (int u : order) if (comp[u] == -1) dfs2(u, nxt_comp++); // pass 2 on G^T
}
```

:::theorem title="Correctness"
Ordering by decreasing finish time visits the SCCs in a **topological order of the condensation** — sources first. Hence in $G^{\mathsf T}$ the first unvisited DFS from a source component $S$ cannot reach any other unvisited component, so it collects exactly $S$.
:::

:::proof
Take two distinct components $A, B$ with an edge $A \to B$ in the condensation. No path $B \leadsto A$ exists (else they'd be one component). Claim: $\operatorname{finish}(A) > \operatorname{finish}(B)$, where $\operatorname{finish}(X)$ is the maximum finish time over $X$.
Case 1 — DFS enters $A$ first: it then reaches all of $A$ and everything $A$ reaches, including $B$; so $B$ finishes inside $A$'s window, strictly earlier than $A$'s exit.
Case 2 — DFS enters $B$ first: $B$'s whole search finishes without reaching $A$ (no path $B \leadsto A$), so $B$ finishes before $A$ even starts.
In the condensation, therefore, decreasing-finish order is a valid topological order. In $G^{\mathsf T}$ every inter-component edge points *backwards* along that order, so a search starting at a source of $G^{\mathsf T}$ (= source component of $G$ in topological order) has its out-edges already assigned. ∎
:::

## Tarjan: one pass, no transpose
Maintain a stack of "still open" vertices plus $\operatorname{low}[u]$ = smallest $\operatorname{tin}$ reachable from $u$'s DFS subtree through open vertices. When $\operatorname{low}[u] = \operatorname{tin}[u]$, pop the stack down to $u$: that is an SCC.

```cpp tarjan-scc.cpp
int timer = 0, ncomp = 0;
vector<int> tin(n, -1), low(n), st, comp(n, -1);
vector<char> on_st(n);
void dfs(int u) {
    tin[u] = low[u] = timer++;
    st.push_back(u); on_st[u] = 1;
    for (int v : g[u]) {
        if (tin[v] == -1) { dfs(v); low[u] = min(low[u], low[v]); }
        else if (on_st[v]) low[u] = min(low[u], tin[v]);   // tin, not low — the classic mistake
    }
    if (low[u] == tin[u]) {
        while (true) { int x = st.back(); st.pop_back(); on_st[x] = 0; comp[x] = ncomp;
                       if (x == u) break; }
        ncomp++;
    }
}
```

| | Kosaraju | Tarjan |
|---|---|---|
| passes | 2 | 1 |
| extra memory | the transpose $G^{\mathsf T}$ | stack + `on_st` |
| code you can re-derive under stress | yes — the proof is a case split | needs the low-link invariant |
| gives components in topological order | yes (naturally, reversed) | yes, in **reverse** topological order |
| iterative-friendly | very | moderately |

:::tip title="Pick by what else you need"
If you also need bridges/articulation points (@foundations/connectivity) you already have low-link machinery — use Tarjan. If you need the transpose anyway (e.g. for reachability or "mother vertex" arguments) Kosaraju's second DFS gives it for free.
:::

## Using the condensation
Once you have `comp[]`, rebuild a DAG on component indices and run any DAG algorithm on it:

```cpp condense.cpp
set<pair<int,int>> dag_edges;
for (auto [u, v] : edges)
    if (comp[u] != comp[v]) dag_edges.insert({comp[u], comp[v]});
// then: longest path, number of sources/sinks, DP over components, etc.
```

:::props title="Three classic one-liners after condensing"
- **Mother vertex**: a vertex reaching all others exists $\iff$ the condensation has exactly one source; test that source's reachability with one DFS.
- **Minimum edges to make strongly connected** (no parallel edges allowed): $\max(\#\text{sources}, \#\text{sinks})$ of the condensation (1 if it is a single vertex) — pair sources to sinks greedily.
- **"Assign a value to each vertex so all cycles agree"**: one value per component; the DAG then carries the constraints.
:::

:::demo id="scc" caption="Two passes with the finish stack and growing component sets visible; switch to Gᵀ to watch pass 2 run on the transpose."
:::

:::problems
- [[CSES 1683]] Planets and Kingdoms | https://cses.fi/problemset/task/1683 | core | output components
- [[CF 427C]] Checkposts | https://codeforces.com/problemset/problem/427/C | core | min cost per SCC
- [[CSES 1705]] Forbidden Cities | https://cses.fi/problemset/task/1705 | hard | SCC + reachability
- [[CSES 1682]] Flight Routes Check | https://cses.fi/problemset/task/1682 | core | one SCC, or exhibit a pair that breaks it
:::