Kosaraju's Algorithm: Two Passes to Find Every SCC in O(V+E)

You have a directed graph. Some nodes can reach each other in both directions, forming little mutual admiration societies. Others only communicate one way, like a person who texts but never replies. Kosaraju's algorithm finds every one of those mutual-reachability groups, and it does it in exactly two DFS passes.

A strongly connected component (SCC) is a maximal set of vertices where every vertex can reach every other. That's the whole definition. Kosaraju finds all of them at once, in linear time, using a trick that feels like cheating: run DFS on the original graph to record finish times, reverse all the edges, then run DFS again in reverse finish order. Each second-pass tree is exactly one SCC.

Reach for it whenever a problem involves mutual reachability in a directed graph, circular dependencies, or the 2-SAT satisfiability problem.

What "Strongly Connected" Actually Means

In an undirected graph, connectivity is simple. Two nodes are connected or they aren't. Directed graphs are messier. An edge from A to B doesn't give you a path from B to A. A can talk to B. B may not even know A exists.

A strongly connected component is the directed analog of a connected component. Within an SCC, you can get from any node to any other node following directed edges. Between different SCCs, you can only travel one way at best.

The condensation graph makes this structure explicit: collapse each SCC into a single node, and the result is always a directed acyclic graph (DAG). It has to be a DAG. If two SCCs had edges going both ways, they would be the same SCC by definition. The universe would collapse.

Three SCCs in the original graph become three nodes in the condensation. The condensation is always a DAG, every time.

The condensation has source SCCs (no incoming edges from other SCCs) and sink SCCs (no outgoing edges). Kosaraju's algorithm is built entirely around locating those sources.

How Kosaraju's Algorithm Works: Two Passes, Every SCC

The whole algorithm is three steps. Run DFS, collect finish times, transpose the graph, run DFS again in reverse finish order. That's it. Every textbook makes it sound harder than it is.

Step 1: DFS on the original graph, recording finish order.

Run a complete DFS, visiting every unvisited node. When DFS finishes with a node (all its descendants have been fully explored), push it onto a stack. The last node pushed has the globally latest finish time.

Graph: 0->1, 1->2, 2->0, 2->3, 3->4, 4->3, 1->5

DFS finish order (bottom to top of stack):
  4 finishes first  (dead end in {3,4} cycle)
  3 finishes next
  2 finishes next   (after exploring {3,4})
  5 finishes next   (leaf, no outgoing)
  1 finishes next
  0 finishes last   <- at the top of the stack

Node 0 is in the source SCC {0,1,2}. It finishes last. Not a coincidence.

Step 2: Build the transposed graph.

Reverse every edge. If the original has edge u→v, the transposed has v→u. The SCCs stay identical (if you could go u→v→u before, you can go u←v←u after), but the edges between SCCs are now flipped. What was a source SCC is now a sink.

Original transposed edges:
  1->0, 2->1, 0->2, 3->2, 4->3, 3->4, 5->1

Step 3: DFS on the transposed graph, popping nodes in reverse finish order.

Pop nodes from the stack. For each unvisited node, run DFS on the transposed graph. All nodes reachable in this DFS belong to one SCC. Mark them visited and collect the next SCC.

Pop 0: DFS on transposed -> visits 0, 2, 1. SCC: {0, 2, 1}
Pop 1: already visited
Pop 5: DFS on transposed -> visits 5. SCC: {5}
Pop 2: already visited
Pop 3: DFS on transposed -> visits 3, 4. SCC: {3, 4}
Pop 4: already visited

Result: [{0,1,2}, {5}, {3,4}]

Three SCCs, found correctly. Two DFS passes.

Why It's Correct: The Finish-Time Lemma

This is where the algorithm earns its elegance. The fact that it works at all is not obvious until you see the proof, at which point it feels obvious in the way only good math does.

The key lemma: if there is an edge from SCC C to SCC C' in the condensation (C can reach C' but not vice versa), then the maximum finish time of any node in C is strictly greater than the maximum finish time of any node in C'.

Proof by two cases. Either DFS enters C first, or it enters C' first.

Case 1: DFS enters C first. From C, DFS follows edges and eventually reaches C'. Nodes in C' get explored and finish. Then DFS unwinds back to C and finishes C's nodes. So max_finish(C) > max_finish(C').

Case 2: DFS enters C' first. DFS can't reach C from C' (no edge C'→C exists by assumption). So C' finishes completely. Later, DFS enters C and possibly follows the C→C' edge, but all of C' is already visited. C finishes later. Again, max_finish(C) > max_finish(C').

Both cases give the same conclusion. Corollary: the node with the globally maximum finish time lives in a source SCC of the condensation. A source SCC has no incoming edges from other SCCs, so it finishes after every SCC it can reach.

Now step 3 makes sense. We pop the node with the maximum finish time. It's in a source SCC. In the transposed graph, a source SCC becomes a sink (all the outgoing edges in the original become incoming edges in the transposed). Starting DFS from a sink SCC in the transposed graph, you can't escape to any other SCC. You visit exactly the nodes in that source SCC.

After marking those nodes visited, the next unvisited node with the maximum remaining finish time is again a source in the remaining condensation. The argument repeats inductively. Every pop peels off one correct SCC.

Six Nodes, Traced Step by Step

Here is the 6-node graph from above, with numbered vertices 0 to 5.

Phase 1 builds the finish-order stack. The source SCC's node lands at the top. Popping it first in Phase 2 is why the whole thing works.

Original edges: 0->1, 1->2, 2->0, 2->3, 3->4, 4->3, 1->5

Phase 1 DFS (start at 0):
  Push (0, idx=0). Mark 0 visited.
  Follow 0->1. Push (1, idx=0). Mark 1 visited.
  Follow 1->2. Push (2, idx=0). Mark 2 visited.
  2->0: 0 already visited. Try 2->3. Push (3, idx=0). Mark 3 visited.
  Follow 3->4. Push (4, idx=0). Mark 4 visited.
  4->3: 3 already visited. No more neighbors.
  Finish 4. finish_order = [4]
  Finish 3. finish_order = [4, 3]
  2 is done. Finish 2. finish_order = [4, 3, 2]
  Back to 1. Follow 1->5. Push (5). Mark 5 visited.
  5 has no neighbors. Finish 5. finish_order = [4, 3, 2, 5]
  Finish 1. finish_order = [4, 3, 2, 5, 1]
  Finish 0. finish_order = [4, 3, 2, 5, 1, 0]

Transposed adjacency list:
  0: [2]      3: [2, 4]
  1: [0]      4: [3]
  2: [1]      5: [1]

Phase 2 (pop from finish_order right-to-left = 0, 1, 5, 2, 3, 4):
  Pop 0: unvisited. DFS on transposed:
    Visit 0 -> follow 0->2 -> visit 2 -> follow 2->1 -> visit 1 -> 1->0 visited.
    SCC: {0, 2, 1}
  Pop 1: visited, skip.
  Pop 5: unvisited. DFS on transposed:
    Visit 5 -> follow 5->1 -> 1 visited.
    SCC: {5}
  Pop 2: visited, skip.
  Pop 3: unvisited. DFS on transposed:
    Visit 3 -> follow 3->2 (visited), 3->4 -> visit 4 -> 4->3 visited.
    SCC: {3, 4}
  Pop 4: visited, skip.

Pop the latest-finishing node, run DFS on the transposed graph, collect everyone you can reach. That's one SCC. Repeat.

Why O(V + E) Is Tight

The O(V + E) bound is tight. Any SCC algorithm must read every vertex and every edge at least once, so O(V + E) is a lower bound. Both DFS passes visit each vertex once (amortized) and each edge once, which gives exactly O(V + E) per pass.

The space is O(V + E) because storing two adjacency lists dominates. The stacks and visited arrays are only O(V).

The one practical cost is that Kosaraju builds the transposed graph explicitly, which uses roughly twice the edge storage of Tarjan's single-pass algorithm. For most graphs this doesn't matter. It's the main tradeoff, and it's worth knowing about when someone asks in an interview why you'd prefer Tarjan.

One Structure, Every Language

from collections import defaultdict

def kosaraju(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
    graph: dict[int, list[int]] = defaultdict(list)
    transposed: dict[int, list[int]] = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)
        transposed[v].append(u)

    visited = [False] * n
    finish_order: list[int] = []

    # Phase 1: iterative DFS to avoid Python's 1000-frame recursion limit
    for start in range(n):
        if visited[start]:
            continue
        stack = [(start, False)]
        while stack:
            node, processed = stack.pop()
            if processed:
                finish_order.append(node)
                continue
            if visited[node]:
                continue
            visited[node] = True
            stack.append((node, True))
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    stack.append((neighbor, False))

    # Phase 2: DFS on transposed in reverse finish order
    visited = [False] * n
    sccs: list[list[int]] = []

    while finish_order:
        start = finish_order.pop()
        if visited[start]:
            continue
        scc: list[int] = []
        stack2 = [start]
        while stack2:
            node = stack2.pop()
            if visited[node]:
                continue
            visited[node] = True
            scc.append(node)
            for neighbor in transposed[node]:
                if not visited[neighbor]:
                    stack2.append(neighbor)
        sccs.append(scc)

    return sccs

What Problems SCCs Actually Solve

Circular dependency detection. Package managers, build systems, and module bundlers need to know whether dependencies form cycles. If packages A, B, and C all depend on each other, they form one SCC and must be built as a unit. The condensation DAG gives you the valid build order. npm, cargo, and Gradle all do some version of this.

2-SAT satisfiability. Any boolean formula of the form "(x OR y) AND (a OR b) AND ..." where each clause has exactly two literals can be solved with SCCs. Build an implication graph: if a clause says "(x OR y)", add edges ¬x→y and ¬y→x (if x is false, y must be true, and vice versa). A 2-SAT formula is satisfiable if and only if no variable x and its negation ¬x appear in the same SCC. This turns an apparently NP-hard-looking problem into a linear-time graph problem, which is one of those moments that makes you grateful someone figured this out before you had to.

Reachability analysis. The condensation DAG lets you answer "from which starting nodes can I reach all other nodes?" cheaply. In the condensation, you need the source SCCs (in-degree zero), and any node within a source SCC in the original graph can reach all other SCCs by following the DAG edges.

Web graph analysis. The web's link structure has a well-known "bow-tie" shape: a giant SCC containing billions of pages, plus tendrils of pages that link into it (or only out of it). PageRank and web crawlers both benefit from SCC decomposition to identify this structure.

Deadlock detection in operating systems. Processes waiting for resources form a directed graph. A cycle in this graph means deadlock. Finding SCCs with more than one node (or self-loops) identifies the deadlocked processes. The OS scheduler is basically running graph algorithms at you all day.

Game theory. In combinatorial games, positions form directed graphs where edges are legal moves. An SCC of game positions represents a cluster from which any position is reachable from any other, which has implications for forced-win analysis.

Five Signals This Is an SCC Problem

1. The problem involves directed edges and asks about "mutual reachability" or "can both get to each other."
2. You need to detect cycles in a dependency structure, then process the cycles as units.
3. A problem says "find all groups where X" in a directed graph, where X involves everyone reaching everyone.
4. You see the phrase "2-SAT" or a structure with boolean implications.
5. The problem asks for the minimum number of nodes from which you can reach all other nodes in a directed graph.

When you see "minimum starting nodes to reach everything," think: count the SCCs with in-degree zero in the condensation.

Worked Example 1: Minimum Nodes to Reach All Nodes

Problem: given a directed graph with n nodes and edges, find the minimum set of nodes from which all nodes are reachable.

Why SCCs fit: within an SCC you can reach every other node in the component from any starting point. Between SCCs, you can only travel downward in the condensation DAG. So you need at least one starting node per source SCC (in-degree zero in the condensation). You never need more.

def min_start_nodes(n, edges):
    sccs = kosaraju(n, edges)
    # Map each node to its SCC index
    scc_of = [0] * n
    for scc_idx, scc in enumerate(sccs):
        for node in scc:
            scc_of[node] = scc_idx

    # Count in-degree of each SCC in condensation
    in_degree = [0] * len(sccs)
    for u, v in edges:
        if scc_of[u] != scc_of[v]:
            in_degree[scc_of[v]] += 1

    # Source SCCs have in-degree 0
    return sum(1 for d in in_degree if d == 0)

For a DAG with n nodes and no edges, this returns n (every node is its own source SCC). For a single large SCC, it returns 1.

Worked Example 2: 2-SAT

Problem: you have n boolean variables and m clauses. Each clause is a disjunction of exactly two literals (a literal is a variable or its negation). Is there an assignment satisfying all clauses?

Why SCCs fit: each clause "(x OR y)" encodes two implications: "¬x → y" and "¬y → x." Build a directed implication graph on 2n nodes (one for each variable and its negation). Run Kosaraju. If any variable x and its negation ¬x land in the same SCC, the formula is unsatisfiable (setting x true forces ¬x true, contradiction). Otherwise, assign x = true if ¬x finishes before x in the topological order of the condensation.

def two_sat(n_vars, clauses):
    # Node 2*i = variable i, node 2*i+1 = negation of i
    edges = []
    for x, y in clauses:
        # x is encoded as 2*|x| if positive, 2*|x|+1 if negative
        # Clause (x OR y) adds edges (not_x -> y) and (not_y -> x)
        not_x = x ^ 1
        not_y = y ^ 1
        edges.append((not_x, y))
        edges.append((not_y, x))

    sccs = kosaraju(2 * n_vars, edges)
    scc_of = [0] * (2 * n_vars)
    for idx, scc in enumerate(sccs):
        for node in scc:
            scc_of[node] = idx

    for i in range(n_vars):
        if scc_of[2 * i] == scc_of[2 * i + 1]:
            return False  # variable and its negation in same SCC
    return True

The check is exact: satisfiability is equivalent to no variable sharing an SCC with its negation.

Kosaraju or Tarjan?

Tarjan's algorithm finds SCCs in a single DFS using low-link values and a stack. One pass instead of two, no transposed graph, lower constant factors. It's the default in competitive programming for those reasons.

Kosaraju wins on conceptual clarity. The two-pass structure maps directly to the proof: finish times encode the condensation's topological order, and the transposed graph blocks cross-SCC movement. If you're in an interview and someone asks you to explain your approach before writing a line of code (which you should expect), Kosaraju is the one you can actually narrate without losing the thread. You'll hear yourself say "the source SCC finishes last, and reversing the edges traps the DFS inside it" and it will make sense as you say it.

Both are O(V + E). For practical graph sizes the difference is negligible. Pick Kosaraju when you want code that explains itself.

The Algorithm With Two Names

S. Rao Kosaraju developed this algorithm in 1978 but never published it. Micha Sharir independently discovered the same approach and published it in 1981. Aho, Hopcroft, and Ullman credited the unpublished 1978 paper in their textbook, which is how Kosaraju's name stuck. The algorithm is sometimes called the Kosaraju-Sharir algorithm in the literature. Both people are fine with this. Presumably.

Tarjan found his version in 1972, earlier than either of them, which is why it's one DFS instead of two. When you've been thinking about graphs long enough, you stop needing the second pass.

Recap

• An SCC is a maximal group of vertices that are mutually reachable in a directed graph.
• Collapsing SCCs into nodes gives the condensation graph, which is always a DAG.
• Phase 1: DFS on the original graph, push nodes to a stack as they finish. The node with the latest finish time is in a source SCC.
• Phase 2: DFS on the transposed graph, popping from the stack. Each DFS tree is exactly one SCC.
• Correctness rests on one lemma: if C can reach C', then max_finish(C) > max_finish(C'). Source SCCs finish last and become sinks in the transposed graph.
• Time: O(V + E). Space: O(V + E).
• Main cost over Tarjan: building and storing the transposed graph.
• Core applications: 2-SAT, circular dependency detection, minimum starting nodes, deadlock detection.
• Pattern signal: mutual reachability in directed graphs, or any problem that reduces to "find cycles and process them as units."

If you want to practice recognizing and implementing Kosaraju under realistic interview conditions, SpaceComplexity runs voice-based mock interviews where you explain your approach out loud before writing a line of code. That's where the pattern recognition actually gets trained.

See also:

• The depth-first search deep dive for the DFS foundation that both passes rely on.
• Topological sort, which is doing something very similar: using DFS finish times to impose an order on a DAG.
• Graph data structure fundamentals for adjacency list representation and the basics of graph traversal.

Further Reading

• Kosaraju's algorithm, Wikipedia: algorithm pseudocode and historical attribution.
• Strongly connected component, Wikipedia: formal definitions, properties, and comparison of all three major SCC algorithms.
• Strongly Connected Components, GeeksforGeeks: worked examples with diagrams and multiple implementations.
• 2-Satisfiability, Wikipedia: how 2-SAT reduces to SCC, with the full proof of correctness.
• 2-SAT Problem, GeeksforGeeks: step-by-step walkthrough of building the implication graph and reading off a satisfying assignment.