Graph AlgosAlgorithmaka SCC, condensation graph

Strongly Connected Components

Maximal vertex sets of a directed graph in which every vertex can reach every other; computed in linear time by Tarjan or Kosaraju.

▶ VisualizePattern: Depth-First SearchPractice (2)
Progress

Overview

In a directed graph, vertices u and v are strongly connected if there is a directed path from u to v *and* from v to u. This relation is an equivalence relation, so it partitions the vertices into strongly connected components (SCCs). A single vertex with no cycle through it is an SCC on its own.

Contracting every SCC into one super-vertex yields the condensation graph, which is always a DAG (Directed Acyclic Graph). This is the key structural fact: any directed graph is "a DAG of cycles". Many problems on general directed graphs (reachability counts, 2-SAT, "which vertices can reach everything") become easy once you work on the condensation.

Two linear-time algorithms compute SCCs: Tarjan's SCC Algorithm (one DFS with low-link values and an explicit stack) and Kosaraju's Algorithm (two DFS passes, the second on the reversed graph). Both are O(V + E). Tarjan is a single pass and emits components in reverse topological order of the condensation; Kosaraju is easier to prove and emits them in topological order.

directedSCCcondensationDAGreachability

Intuition

A mental model before the formal terms.

Think of a road network of one-way streets. A strongly connected component is a district you can drive around freely: from any corner you can reach any other corner and come back. Between districts, though, the one-way streets only let you travel in one direction overall — once you leave a district you can never return to it (if you could, the two districts would be one). So zooming out, the districts form a map with no round trips: a DAG.

A component count is a measure of how "cyclic" the graph is: n components means no directed cycle at all (the graph is a DAG); one component means every vertex sits on a cycle through every other.

How it works

  1. Choose an algorithm: Tarjan's SCC Algorithm tracks, for each vertex, the smallest DFS index reachable through the current DFS subtree plus one back edge; a vertex whose low-link equals its own index is the root of an SCC. Kosaraju's Algorithm records DFS finish order, reverses all edges, and runs DFS in decreasing finish order — each DFS tree on the reversed graph is one SCC.
  2. Both yield comp[v], a component id per vertex. Tarjan numbers components in reverse topological order of the condensation (sinks first); Kosaraju numbers them in topological order (sources first).
  3. Build the condensation: for every edge (u, v) with comp[u] != comp[v], add edge (comp[u], comp[v]) to the DAG (deduplicate with a set if needed).
  4. Solve the original problem on the DAG, usually with a Topological Sort and DP on DAGs — e.g. "minimum vertices to add so everything is reachable" = number of source components (when the condensation has more than one node).

Why it works

The condensation is acyclic because a cycle through components C1 → C2 → … → C1 would make every vertex in those components mutually reachable, contradicting maximality of each SCC.

Both Tarjan and Kosaraju rely on the same fact about DFS: the vertices of an SCC always form a contiguous subtree of the DFS forest, rooted at the first SCC vertex the DFS entered. Tarjan finds that root via low-links; Kosaraju isolates the subtree by traversing the reverse graph from the vertex that finished last.

Recognition

How to tell a problem wants this.

  • A directed graph and questions about "mutual reachability", "can get there and back", "circular dependencies between modules".
  • "Minimum edges to add so that every node is reachable from node 0" or "number of nodes from which all others are reachable" — count sources/sinks of the condensation.
  • 2-SAT: variable x and ¬x in the same SCC of the implication graph means unsatisfiable.
  • Any directed-graph problem that would be easy on a DAG: condense first, then use DAG techniques.
“connected groups” → Depth-First Search“prerequisites” → Topological Sort

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Tarjan's SCC Algorithm visualization.

ABCDEFGH
Stack (top → bottom)
empty
SCCs found
empty
1/29Tarjan runs one DFS. Each node gets a discovery index and a low-link; when they coincide the node roots an SCC, which is exactly what sits above it on the stack.
Current node (label = idx/low)On the stackIn a completed SCCDFS tree edgeBack edge lowering low
PseudocodeLearn Tarjan's SCC Algorithm →
1index = 0; stack = []
2def strongconnect(u):
3  idx[u] = low[u] = index; index += 1; stack.push(u); onStack[u] = true
4  for v in neighbors(u):
5    if v unvisited: strongconnect(v); low[u] = min(low[u], low[v])
6    elif onStack[v]: low[u] = min(low[u], idx[v])
7  if low[u] == idx[u]:
8    pop stack down to u → one SCC
9for u in nodes: if u unvisited: strongconnect(u)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1comp = tarjan(adj)      # or kosaraju(adj)
2k = number of components
3dagAdj = k empty lists
4for u in 0..n-1:
5  for v in adj[u]:
6    if comp[u] != comp[v]: dagAdj[comp[u]].add(comp[v])
7return comp, dagAdj    # dagAdj is acyclic

Implementations

1# Conceptual topic: given comp[v] (from tarjan_scc or kosaraju), build the
2# condensation DAG and count its source components — the classic
3# "minimum edges to add so everything is reachable from src" application.
4 
5 
61 · Build the condensation DAG from component ids
7def condensation(n: int, adj: list[list[int]], comp: list[int]) -> list[set[int]]:
8    k = max(comp) + 1
9    dag: list[set[int]] = [set() for _ in range(k)]
10    for u in range(n):
11        for v in adj[u]:
12            if comp[u] != comp[v]:
13                dag[comp[u]].add(comp[v])
14    return dag
15 
16 
17def min_edges_to_reach_all_from(n: int, adj: list[list[int]], comp: list[int], src: int) -> int:
182 · In-degree of every component node
19    dag = condensation(n, adj, comp)
20    k = len(dag)
21    indeg = [0] * k
22    for targets in dag:
23        for d in targets:
24            indeg[d] += 1
25 
263 · Count source components other than src's
27    return sum(1 for c in range(k) if indeg[c] == 0 and c != comp[src])
Walkthrough
  1. Representative application of SCCs; comp comes from tarjan_scc / kosaraju.
  2. max(comp) + 1 is the component count; a list of sets deduplicates DAG edges.
  3. Intra-component edges are filtered so the DAG has no self-loops.
  4. In-degrees are accumulated over each target set.
  5. A generator expression counts sources other than comp[src].
Complexity (this implementation)
time O(V + E) · space O(V + E)
Language notes
  • set.add is average O(1); [set() for _ in range(k)] creates independent sets.
  • collections.defaultdict(set) is convenient when component ids are sparse.
Common mistakes in this language
  • [set()] * k aliases one set across all components.
  • Missing the comp[u] != comp[v] filter.
  • Assuming Tarjan and Kosaraju number components the same way.
Language differences that matter here
  • C++ std::set is ordered (O(log k) insert); JS/TS Set and Python set are hash-based (O(1) average).
  • JS Math.max(...comp) has an argument-count limit; the TS version uses a loop, Python max() takes an iterable directly, C++ uses std::max_element.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V + E)

Either Tarjan or Kosaraju; building the condensation is another O(V + E).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Directed graph questions about mutual reachability or cycles of dependencies.
  • Reducing a general directed graph to a DAG so that Topological Sort / DP on DAGs techniques apply.
  • 2-SAT, finding all vertices on some cycle, or counting vertices that can reach every other vertex.
Avoid it when
  • Undirected graphs — every component is trivially strongly connected; use Connected Components.
  • You only need to know whether *a* cycle exists, not the component structure — Cycle Detection with three colours is simpler.
  • Edge-connectivity questions ("which single edge disconnects the graph") — that is Bridges, a different low-link algorithm.

Alternatives

Tarjan's SCC AlgorithmKosaraju's AlgorithmConnected ComponentsCycle Detection

Common mistakes

  • Confusing weak connectivity (ignore directions) with strong connectivity; a directed path 0 → 1 → 2 has one weak component but three SCCs.
  • Adding self-loops or duplicate edges to the condensation because comp[u] == comp[v] was not filtered out.
  • Assuming Tarjan and Kosaraju number components in the same order — Tarjan is reverse-topological, Kosaraju is topological.

Interview patterns

  • Condense, then count source components (in-degree 0) or sink components (out-degree 0).
  • Detect whether the whole graph is strongly connected: exactly one SCC.
  • 2-SAT via implication graph: satisfiable iff no variable shares an SCC with its negation.
Interview questions on this
Mock interviews

Example problems

Critical Connections in a NetworkhardCourse Schedulemedium