A Strongly Connected Component (SCC) is a maximal group of nodes in a directed graph where every node can reach every other node within the group — think of friends where each can contact each other directly or indirectly.

Kosaraju’s algorithm finds every SCC in linear time with a deceptively simple two-pass DFS. The trick: a finish-time ordering from the first pass lets the second pass on the reversed graph peel off components one at a time.

How It Works

1. First pass (finish order): run DFS on the original graph, pushing each node onto a stack when its exploration finishes.
2. Build the reverse graph: flip the direction of every edge.
3. Second pass (reverse DFS): pop nodes from the stack; for each unassigned node, run DFS on the reverse graph. Each DFS tree produced is exactly one SCC.

Key Insight

Why does reversing edges do the magic? The finish order from pass one sorts nodes so that, in the reversed graph, you always pop a node in a source component of the condensation DAG first.

Since the reverse graph turns original sinks into sources, a single reverse-DFS from a popped node stays trapped inside its own component — it can never leak into an already-assigned one. Two linear passes = O(V + E), no heuristics.

Worked Example

Run Kosaraju’s on the visualizer’s directed graph (A–G):

Pass 1 (DFS finish order, one possible result): A, B, C form a cycle; D↔E form one; F↔G form one. A finish-order stack might read [C, B, A, E, D, G, F].

Pass 2 (reverse graph, pop from the top):

• Pop F → reverse-DFS reaches {F, G} → SCC₁ = {F, G}.
• Pop D → reverse-DFS reaches {D, E} → SCC₂ = {D, E}.
• Pop A → reverse-DFS reaches {A, B, C} → SCC₃ = {A, B, C}.

Result: 3 SCCs — watch the visualizer color each group as its reverse-DFS completes.

Condensation Graph

Contracting each SCC to a single node produces a DAG — by construction it cannot contain a cycle. This is where SCCs earn their keep: problems like “how many edges are needed to make the whole graph strongly connected” reduce to counting sources and sinks of the condensation DAG.

Edge Cases & Pitfalls

• Single-node SCCs — isolated or acyclic nodes each form a size-1 component: correct, not an error.
• Whole graph is one SCC — the first and last reverse-DFS trees are the same single component.
• Disconnected graphs — Kosaraju handles them naturally: each DFS in each pass covers only its own region.
• Finish order correctness — the stack must be built from completion (postorder), not discovery order, or the second pass fails.

Comparison: Kosaraju vs Tarjan

Applications

• Dependency analysis — finding cycles in module/build graphs
• 2-SAT solvers — satisfiability reduces to SCC ordering
• Compilers — computing sets of mutually recursive functions
• Data pipelines — collapsing cycles to process stages in DAG order

Practice Trajectory

1. Find the SCCs of the visualizer’s directed graph by hand using finish-order + reverse.
2. Trace each color group — confirm every group is one reverse-DFS tree.
3. Contract the components and verify the result is a DAG.
4. Explain why the first pass must record completion order, not discovery order.
5. Count sources and sinks of the condensation DAG to derive the edges-to-strong-connect formula.