Kosaraju's Algorithm: Strongly Connected Components Guide

TL;DR: Kosaraju's algorithm finds strongly connected components in a directed graph using two depth-first-search passes. First record vertices by decreasing finish time, transpose every edge, then explore the transposed graph in that order. The runtime is O(V + E) and the auxiliary storage is O(V + E) when the transpose is stored.

What is Kosaraju's algorithm?

Kosaraju's algorithm partitions a directed graph into strongly connected components, or SCCs. Inside one SCC, every vertex can reach every other vertex. Contracting each SCC into one node produces a directed acyclic graph, which makes the components useful for dependency analysis, program graphs, reachability, and graph condensation.

The algorithm uses a structural property of depth-first search. Finish times from the original graph identify a safe order for exploring the transposed graph. Reversing every edge swaps source and sink relationships between components, so one search cannot leak into an unassigned component when vertices are processed in the correct order.

How does the two-pass algorithm work?

1. Create a visited set and an empty finish-order list.
2. Run depth-first search from every unvisited vertex in the original graph.
3. Append each vertex after all of its outgoing neighbors finish.
4. Build the transpose by reversing every directed edge.
5. Clear the visited set.
6. Process vertices in reverse finish order.
7. Each DFS tree in the transposed graph is one strongly connected component.

You can store vertices on a stack when their first DFS call returns. Popping the stack naturally gives decreasing finish time. The graph may be disconnected, so both outer loops must consider every vertex rather than starting from vertex zero only.

Why does reversing finish order find SCCs?

Imagine compressing every SCC into a single node. The resulting condensation graph has no directed cycle. In the first DFS, the component with the latest relevant finish time behaves like a source in this condensed structure. After transposing the graph, that component behaves like a sink, so a DFS begun there remains inside it.

Removing that component reveals the same argument for the next unassigned component. This is the proof idea interviewers usually want: finish order selects components safely, and transposition prevents the second pass from crossing the wrong outgoing boundary. You do not need to reproduce a long formal proof, but you should explain both roles.

What are the time and space complexities?

Each depth-first-search pass visits every vertex and examines every edge once, and constructing the transpose also takes linear time. Therefore the total time is O(V + E). With adjacency lists for both the graph and transpose, storage is O(V + E), plus O(V) for visited state, finish order, and recursion or an explicit stack.

For very deep graphs, recursive DFS can exceed a language's call-stack limit. Mentioning an iterative stack shows production awareness without changing the asymptotic bound.

What pseudocode should you know for an interview?

finish_order = []
visited = set()

for vertex in graph:
    if vertex not in visited:
        dfs_finish(vertex, graph, visited, finish_order)

transpose = reverse_all_edges(graph)
visited.clear()
components = []

for vertex in reverse(finish_order):
    if vertex not in visited:
        component = []
        dfs_collect(vertex, transpose, visited, component)
        components.append(component)

In dfs_finish, append the vertex after visiting neighbors. In dfs_collect, add the vertex when it is discovered. Keep those two responsibilities separate; using preorder in the first pass is a common error.

Which mistakes commonly break a Kosaraju implementation?

The most common mistakes are recording discovery order instead of finish order, forgetting to reverse the order for the second pass, reversing only some edges, reusing visited state without clearing it, and skipping isolated or disconnected vertices. Another mistake is treating an undirected graph as if SCCs were meaningful in the same way; connected components are the simpler concept there.

Test a single vertex, an isolated vertex, one directed cycle, a one-way chain, two cycles joined by one edge, self-loops, and a disconnected graph. Verify the partition rather than relying on component output order, because different valid DFS traversal orders may list components or vertices differently.

How does Kosaraju compare with Tarjan's algorithm?

Both algorithms find SCCs in O(V + E). Kosaraju uses two DFS passes and usually stores a transposed graph, which can make the reasoning and implementation straightforward. Tarjan uses one DFS with discovery indices, low-link values, and a stack; it avoids an explicit transpose but has more state to maintain correctly.

In an interview, choose the algorithm you can explain and implement reliably unless constraints favor one. If the interviewer asks for one pass or no transpose, Tarjan may fit better. If clarity and a direct proof are priorities, Kosaraju is often an excellent choice.

How can AI support graph-algorithm practice responsibly?

AI can generate small counterexamples, trace DFS state, compare implementations, and challenge a complexity explanation. Coding assistance can help locate an ordering or visited-state bug, while transcript review can show whether you explained the proof idea clearly.

Always draw and trace at least one graph yourself, run tests, and verify generated claims. Follow assessment rules and do not use prohibited assistance. YesToTheOffer supports coding preparation, permitted real-time reasoning, private notes, and post-interview review.

Frequently asked questions

Turn practice into a repeatable system

Build an evidence-based practice plan, use responsible support where permitted, and review the conversation while it is fresh.