Kosaraju's Algorithm: Strongly Connected Components Guide

Kosaraju's algorithm finds the strongly connected components (SCCs) of a directed graph. An SCC is a group of vertices where every vertex can reach every other one. The algorithm runs two depth-first searches: the first records the order in which vertices finish, and the second runs on the graph with every edge reversed, taking vertices in reverse finish order. Each tree of the second search is one SCC. It runs in O(V + E) time.

If you squash each SCC into a single node, what's left is a directed graph with no cycles. That's why SCCs show up in dependency analysis, deadlock detection, 2-SAT, and any problem where cycles need to be collapsed first.

The two passes, step by step

1. Run DFS over the whole graph. When a vertex finishes (all its outgoing neighbors are done), push it onto a list.
2. Reverse every edge to get the transpose graph.
3. Go through the finish list from last to first. For each vertex not yet visited, run DFS on the transpose graph. Everything that search reaches is one SCC.

Both loops have to start from every unvisited vertex, not only from vertex 0, because the graph may not be connected.

A worked example

Take 8 vertices and these edges:

0 → 1, 1 → 2, 2 → 0      (cycle A: 0, 1, 2)
2 → 3
3 → 4, 4 → 5, 5 → 3      (cycle B: 3, 4, 5)
6 → 5
6 → 7, 7 → 6             (cycle C: 6, 7)

The SCCs should be 2, 5, and 7.

First pass

Start DFS at 0 and go 0 → 1 → 2 → 3 → 4 → 5. Vertex 5 has nowhere new to go, so it finishes first, then 4, then 3. Back at 2 there's nothing left, so 2, 1, and 0 finish. Vertex 6 hasn't been visited, so start there: 5 is already done, so go to 7, which finishes, then 6. The finish order is:

5, 4, 3, 2, 1, 0, 7, 6

Second pass

Reverse every edge and process vertices from the end of that list: 6 first. In the reversed graph, 6 can only reach 7, so 7 is the first SCC. Next unvisited is 0, which reaches 2 and 1 in the reversed graph, giving 2. The edge 2 → 3 now points 3 → 2, but 2 is already assigned, so the search stops there. Last, 3 reaches 5 and 4, giving 5.

Why it works

Think of the graph of SCCs (each component collapsed to one node), which has no cycles. In the first pass, the vertex that finishes last always belongs to a "source" component, one with no edges coming in from other unassigned components. Reversing the edges turns that source into a sink, so a DFS started there can't leave its own component. Once that component is removed, the same argument applies to the next one.

In an interview, that's usually the level of proof expected: finish order picks a safe starting component, and reversing the edges keeps the second search from leaking into other components.

Python implementation

This version uses iterative DFS, so it won't hit Python's recursion limit on deep graphs.

from collections import defaultdict

def kosaraju(n, edges):
    graph = defaultdict(list)
    reverse = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        reverse[v].append(u)

    # Pass 1: record vertices in the order they finish (iterative DFS)
    visited = [False] * n
    order = []
    for start in range(n):
        if visited[start]:
            continue
        visited[start] = True
        stack = [(start, iter(graph[start]))]
        while stack:
            node, neighbors = stack[-1]
            for nxt in neighbors:
                if not visited[nxt]:
                    visited[nxt] = True
                    stack.append((nxt, iter(graph[nxt])))
                    break
            else:
                stack.pop()
                order.append(node)

    # Pass 2: DFS on the reversed graph, latest finish time first
    visited = [False] * n
    components = []
    for start in reversed(order):
        if visited[start]:
            continue
        visited[start] = True
        component = []
        stack = [start]
        while stack:
            node = stack.pop()
            component.append(node)
            for nxt in reverse[node]:
                if not visited[nxt]:
                    visited[nxt] = True
                    stack.append(nxt)
        components.append(component)
    return components


edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (6, 5), (6, 7), (7, 6)]
print(kosaraju(8, edges))  # [[6, 7], [0, 2, 1], [3, 5, 4]]

The order of vertices inside each component depends on the traversal, so compare components as sets in your tests. We checked this implementation against a brute-force reachability check on 2,000 random graphs.

Complexity

Space is O(V + E) for the two adjacency lists, plus O(V) for the visited array, the finish order, and the stack.

Mistakes that break it

The most common bug is recording vertices when DFS first reaches them instead of when they finish. Others are forgetting to reverse the finish order for the second pass, running the second pass on the original graph instead of the reversed one, not clearing the visited array between passes, and only starting from vertex 0 so disconnected parts get skipped. Recursive DFS can also overflow the stack on long chains, which is why the code above is iterative.

Good test cases: a single vertex, a vertex with a self-loop, one big cycle, a one-way chain (every vertex is its own SCC), two cycles joined by one edge, and a disconnected graph.

Kosaraju vs. Tarjan

Both run in O(V + E). Kosaraju makes two passes and builds the reversed graph, which makes it easier to explain and to get right. Tarjan's algorithm does it in one pass with no reversed graph, but tracks discovery indexes and low-link values on a stack, which is more state to keep straight. In an interview, use whichever you can implement correctly and explain. If the interviewer asks for a single pass, that's a cue for Tarjan.

Practicing graph problems

Trace the example above by hand once before writing code; most bugs show up as a wrong finish order. Related guides: Floyd–Warshall for all-pairs shortest paths, Bellman–Ford for graphs with negative edges, and our Big O cheat sheet. If you use YesToTheOffer in coding practice, its screenshot coding help can check your approach, and the session transcript shows whether you explained your reasoning clearly.