Kosaraju's SCC Finder

Pseudocode

Two depth-first searches and one transposed graph. Nothing clever happens inside either pass; all the work is done by the order the second pass runs in.

Kosaraju(graph):
    // Pass 1: record finish order on the original graph
    order = []
    for each unvisited u: dfs1(u)

    dfs1(u): mark u visited
             for each edge (u,v): if unvisited: dfs1(v)
             order.append(u)          // on finish

    // Pass 2: DFS the transpose in reverse finish order
    gt = transpose(graph)      // reverse every edge
    for each u in reverse(order):
        if u unvisited:
            the tree grown from u in gt is one SCC

Why it works: reversing every edge leaves the strongly connected components untouched, since if you could get from x to y and back before, you still can. What reversal does change is the direction of the edges between components. Starting from the vertex that finished last guarantees you begin in a component that is a source of the condensation, so the second DFS cannot leak out of it into another component.

Worked example, step by step

Run Kosaraju on the same directed graph used for the Tarjan example, so the two can be compared directly.

Example graph: Directed edges A to B, B to C, C to A, B to D, D to E, E to D, and C to F.

1. Pass 1 from A. Descend A, B, C, then C to A is already visited so take C to F. F has no outgoing edges and finishes first. C finishes next, then the search backtracks to B and takes B to D, then D to E, and E to D is already visited so E finishes, then D, then B, then A.
2. Finish order. Vertices finish in the order F, C, E, D, B, A. Reversing gives the processing order for pass 2: A, B, D, E, C, F.
3. Transpose the graph. Every edge flips: B to A, C to B, A to C, D to B, E to D, D to E, F to C.
4. Pass 2 starting at A. In the transpose, A reaches C, and C reaches B, and B only reaches A which is already visited. The tree covers A, C and B, so the first component is {A, B, C}. Crucially the search could not escape into D or F, because in the transpose those edges point inward, not outward.
5. Pass 2 continues. The next unvisited vertex in the order is D. In the transpose D reaches B, already visited, and E, which reaches D, already visited. The component is {D, E}. Finally F is unvisited: in the transpose it reaches only C, already visited, so it is the singleton {F}.

The components are {A, B, C}, then {D, E}, then {F}. Compare this with Tarjan on the same graph, which emits {F}, then {D, E}, then {A, B, C}. Both are correct and both find the same three components, but Kosaraju emits them in forward topological order of the condensation while Tarjan emits them in reverse. If the order matters to your downstream code, that difference is the reason to pick one over the other.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V + E)

Two depth-first searches cost O(V + E) each, and building the transposed graph requires one pass over all edges, also O(V + E). Summing gives O(V + E) overall. The space is where Kosaraju genuinely loses to Tarjan: it must store the transposed adjacency structure, which is a second full copy of the edge list at O(V + E), whereas Tarjan needs only O(V) of bookkeeping on top of the original graph. On a graph with tens of millions of edges that difference is the deciding factor, which is why Tarjan tends to win in production even though the two are asymptotically identical in time.

When to use Kosaraju's SCC Algorithm, and when not to

All the linear SCC algorithms cost O(V + E). The trade-offs are memory, number of passes, and how easy the code is to get right.

Common pitfalls

• Using the finish order forwards instead of reversed. The second pass must process vertices in decreasing finish time. Running it in increasing order starts inside a sink component and the DFS spills across component boundaries, merging separate SCCs into one. This is the defining Kosaraju bug.
• Appending to the order at discovery rather than at finish. The vertex must be pushed when its recursion completes, not when it is first reached. Discovery order carries none of the information the algorithm depends on.
• Forgetting to reset the visited set between passes. The two searches are independent. Carrying the first pass visited marks into the second means nothing is ever explored and every component comes back empty.
• Transposing in place. The second pass needs the reversed graph while the finish order came from the original. Mutating the original adjacency lists rather than building a separate transpose corrupts both.
• Assuming it works on undirected graphs. Strong connectivity is a directed notion. On an undirected graph every connected component is trivially strongly connected, and a single DFS or Union-Find answers the question far more cheaply.

Frequently asked questions

How does Kosaraju's algorithm work?

It runs a depth-first search on the original graph and records the order in which vertices finish. It then reverses every edge and runs a second depth-first search, processing vertices in decreasing finish order. Each tree grown in the second pass is exactly one strongly connected component.

Why does reversing the edges work?

Reversing edges preserves strong connectivity, since a round trip between two vertices still exists when every edge flips. What it does change is the direction between components. Starting from the last-finishing vertex puts you in a source component of the condensation, and after reversal its outgoing links become incoming, so the search is trapped inside the component and cannot leak out.

What is the difference between Kosaraju and Tarjan?

Both are O(V + E). Kosaraju uses two DFS passes plus a transposed copy of the graph, so it needs O(V + E) extra space; Tarjan uses one pass and O(V) extra space. Kosaraju is easier to explain and implement, Tarjan is faster and lighter in practice. They also emit components in opposite orders: Kosaraju in forward topological order of the condensation, Tarjan in reverse.

What is the time complexity of Kosaraju's algorithm?

O(V + E) time, from two linear traversals plus one linear pass to build the transpose. Space is O(V + E) because the transposed graph must be stored, which is the main practical difference from Tarjan.

Can Kosaraju find components in an undirected graph?

It would work but it is pointless. In an undirected graph every connected component is already strongly connected, so one DFS or a Union-Find structure finds them in a single pass without building a transpose.