Strongly Connected Components (Kosaraju's Algorithm)

Implement Kosaraju's algorithm to find all strongly connected components in a directed graph.

graphs dfs kosaraju components directed

A directed graph is strongly connected if there is a path between every pair of vertices. A strongly connected component (SCC) is a maximal set of vertices where every vertex is reachable from every other vertex.

Implement the function `kosaraju_scc(n, edges)` that returns a list of SCCs. The graph has `n` vertices labeled from `0` to `n-1`, and `edges` is a list of tuples `(u, v)` representing a directed edge from `u` to `v`. The graph may contain multiple edges or self-loops.

Your function must return a list of lists, where each inner list contains the vertices in one SCC. The order of the SCCs and the order of vertices within each SCC do not matter, but the sets of vertices must be exactly correct. The output must be sorted for comparison: each inner list sorted ascending, and the outer list sorted by the first element of each inner list.

Use Kosaraju's algorithm: first perform DFS on the original graph to get a finishing order, then DFS on the reversed graph in that order to extract components. The graph must be handled correctly even when `n = 0` (return an empty list).

Constraints

- `n` is an integer with `0 <= n <= 1000`.
- `edges` may contain any number of edges (including zero).
- Each edge is a pair `(u, v)` with `0 <= u, v < n`.
- The graph may have self-loops and parallel edges.
- The output must be sorted as specified: each inner list sorted ascending, outer list sorted by first element (and if tie, next element, etc.). The test cases use this normalized format.

Example

>>> kosaraju_scc(5, [(0,1),(1,2),(2,0),(1,3),(3,4)])
[[0, 1, 2], [3], [4]]
>>> kosaraju_scc(3, [])
[[0], [1], [2]]
>>> kosaraju_scc(1, [])
[[0]]
>>> kosaraju_scc(0, [])
[]

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Build the reverse graph: for each edge (u, v), add (v, u) to the reversed adjacency list.

Perform iterative DFS on the original graph to compute the finishing order, handling the case n=0.

Process vertices in reverse finishing order, running DFS on the reversed graph. Each DFS tree is one SCC.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.