Kosaraju's Algorithm (Strongly Connected Components)

Given a directed graph with V vertices (0 .. V-1) and directed edges edges, return the number of strongly connected components (SCCs) — maximal groups of vertices in which every vertex can reach every other.

Hints

· Stuck? Reveal one nudge at a time.

An SCC is a maximal set where every vertex reaches every other (directed).

Kosaraju: DFS by finish time, then DFS the transpose in reverse order.

Tarjan: one DFS with discovery times and low-links; an SCC root has low[u] == disc[u].

Common doubts

Processing the transpose in reverse finish order guarantees each DFS tree stays within one SCC, so the tree count equals the SCC count.

The smallest discovery time reachable from u's subtree using tree edges and one back edge to a vertex still on the stack.

Both are O(V+E). Tarjan needs a single pass and no transpose; Kosaraju is often considered simpler to reason about.

Interview follow-ups

· What an interviewer asks next.

Collect the vertices of each transpose DFS tree (Kosaraju) or each popped stack segment (Tarjan).

Contract each SCC to a single node; the result is always a DAG.

Fun facts

Tarjan's SCC algorithm (1972) was among the first to exploit DFS low-links — the same idea behind bridges and articulation points.
The condensation of any directed graph into SCCs is a DAG, which is why 2-SAT reduces to SCCs.

Asked at

GoogleAmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: V = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]
Output: 3
{0,1,2} is one SCC; {3} and {4} are singletons.

Example 2

Input: V = 3, edges = [[0,1],[1,2],[2,0]]
Output: 1
The whole cycle is one strongly connected component.

Constraints

- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - edges are directed u -> v - no duplicate edges

A strongly connected component is a maximal set where mutual reachability holds. Two linear algorithms count them:

Kosaraju (two passes). DFS the graph and push each vertex onto a list when it finishes. Then DFS the transpose (every edge reversed) in reverse finish order — each tree you start is exactly one SCC. Intuition: the last-finishing vertex sits in a "sink" SCC of the transpose, so peeling in that order isolates one SCC at a time. O(V + E).

Tarjan (single pass). One DFS tracking disc[u] (discovery time) and low[u] (the earliest-discovered vertex reachable from u via tree edges plus one back edge to a vertex still on the stack). When low[u] == disc[u], u is the root of an SCC — pop the stack down to u. Also O(V + E), with a single traversal.

Prerequisites

Before you start

· Concepts used directly in the solution.

Transpose graph. reverse every edge (Kosaraju).

Discovery time & low-link. Tarjan's SCC machinery.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“What defines an SCC?”

Every vertex reaches every other within it.

“Directed?”

Yes — SCCs are a directed-graph notion.

The ideal opening — say it like this

Kosaraju: DFS by finish time, then DFS the transpose in reverse finish order — each tree is an SCC.

Tarjan does it in one pass with discovery times and low-links, popping an SCC when low equals disc.

Understand the problem

Worked example — V = 5, edges [[0,1],[1,2],[2,0],[1,3],[3,4]]

{0,1,2} are mutually reachable -> one SCC; {3} and {4} are singletons
answer = 3

Key observations

1Aha

Finish order isolates SCCs (Kosaraju)

Reverse finish order on the transpose peels one SCC per tree.

2Aha

low == disc marks an SCC root (Tarjan)

Pop the stack down to it.

3Aha

Both are O(V + E)

Kosaraju does two DFS passes; Tarjan does one.

Brute force vs optimal

	Kosaraju	Tarjan
Passes	two DFS (graph + transpose)	one DFS with low-links
Time	O(V+E)	O(V+E)
Needs transpose

Both count the same SCCs. Full code is in the Approaches selector below.

Summary

Key takeaway

SCCs are maximal mutually-reachable groups. Kosaraju: DFS by finish time, then DFS the transpose in reverse order (one SCC per tree). Tarjan: one DFS, pop an SCC when low[u] == disc[u]. O(V+E).

kosaraju: order by finish; dfs transpose in reverse -> count trees
tarjan: dfs with disc/low; low[u]==disc[u] -> new SCC