Strongly Connected Components (Kosaraju/Tarjan)

Given a **directed graph** with **n** vertices, find all **Strongly Connected Components (SCCs)** — maximal sets of vertices where every vertex can reach every other vertex in the same set.

Implement this using **Kosaraju's algorithm** (two-pass DFS with graph transpose). Return the SCCs as an array of arrays; each inner array lists the vertices in one component.

Examples

Input: n = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]

Output: [[0,1,2],[3],[4]]

0,1,2 form a cycle (one SCC); 3 and 4 are each their own SCC.

Constraints

• 1 <= n <= 2000
• Order of vertices within an SCC and order of SCCs in the output may vary

Complexity Analysis

Time

O(V + E)

two DFS passes (original graph + transpose).

Space

O(V + E) for the adjacency lists, transpose graph, and finish-order stack.

Test Cases

#1 — One cycle plus two singleton SCCs

Input: n=5 edges=[[0,1],[1,2],[2,0],[1,3],[3,4]]

Expected: [[0,1,2],[3],[4]] (order may vary)

#2 — No cycles — every vertex its own SCC

Input: n=3 edges=[[0,1],[1,2]]

Expected: [[0],[1],[2]] (order may vary)

#3 — Two mutually reachable vertices

Input: n=2 edges=[[0,1],[1,0]]

Expected: [[0,1]] (order may vary)

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.