Kosaraju's Algorithm

A Bit of History

Kosaraju's algorithm has one of the more unusual origin stories in this series: computer scientist S. Rao Kosaraju devised it around 1978, but never published it himself — it circulated as an unpublished course handout at Johns Hopkins University. Three years later, in 1981, Micha Sharir independently discovered and published an equivalent two-pass technique in a formal paper. The algorithm is now universally credited to both — "Kosaraju's algorithm" for the original unpublished insight, sometimes "Kosaraju-Sharir" in more careful references — a reminder that an idea circulating informally among students and colleagues can shape a field just as much as a published paper.

SCC Foundations

In a directed graph, reachability is not automatically mutual. A strongly connected component (SCC) is a maximal set $C$ such that every $u,v\in C$ satisfy $u\leadsto v$ and $v\leadsto u$. “Maximal” means no additional vertex can be added while preserving that property.

Transposing a graph reverses every edge: $(u,v)\in E$ becomes $(v,u)\in E^T$. The SCC partition itself does not change, because every path inside an SCC simply reverses into a path in the opposite direction.

Working Principle

Kosaraju's algorithm separates ordering from collection:

1. Order: run DFS on the original graph $G$. Append a vertex only after all reachable unvisited neighbors finish.
2. Reverse: build the transpose $G^T$ by reversing every edge.
3. Collect: process vertices on $G^T$ in decreasing finish time. Every new DFS tree is one SCC.

Finishing-Order Intuition

For a component $C$, define $f(C)$ as the largest finish time among its vertices in Pass 1. If the condensation DAG contains an edge $C\to D$, then $f(C)>f(D)$. Either DFS first reaches $D$ from $C$ and finishes $D$ before returning, or $D$ was already completely finished before $C$ was discovered. In both cases, $C$ finishes later.

Therefore, among unprocessed components, the vertex with largest finish time lies in a source SCC of the original condensation DAG. Transposition makes it a sink. This source-to-sink conversion is the engine of the algorithm.

Worked Example

Take edges $A\to B$, $B\to C$, $C\to A$, $C\to D$, $D\to E$, and $E\to D$. With vertices and adjacency lists visited in the displayed order, the first DFS begins at A and reaches the entire graph.

The exact order inside an SCC can change with adjacency order. What matters is the component-level ordering: every vertex of the source component $\{A,B,C\}$ is processed before an unvisited vertex can seed $\{D,E\}$.

Why the Transpose Trick Works

Consider the first unassigned vertex $v$ in decreasing finish order, and let $C$ be its SCC. By the finishing-time lemma, $C$ is a source among the remaining components of the original condensation DAG. Therefore $C$ is a sink in the remaining condensation DAG of $G^T$.

A DFS starting at $v$ on $G^T$ can reach every vertex in $C$ because transposition preserves strong connectivity. It cannot reach any other unassigned component because $C$ has no outgoing component edge in $G^T$. So the DFS tree is exactly $C$. Mark it assigned and repeat the same argument on the remaining condensation DAG.

Complexity Analysis

Each DFS examines every vertex once and every outgoing edge once. Building the transpose scans the edge list once:

$$\text{Time: } O(V + E) \qquad \text{Space: } O(V + E)$$

The output itself can contain all $V$ vertices. Recursive DFS may also use $O(V)$ call-stack frames on a long path; an iterative frame stack is safer when graphs can be deep.

Implementation

There are two details worth checking against the code:

• Every vertex must participate in Pass 1. Loop over the complete vertex set so isolated vertices become singleton SCCs.
• Append after recursion. finish_order.append(u) belongs after every outgoing neighbor has been processed.

from collections import defaultdict

def kosaraju_scc(vertices, edges):
    """Return the SCC partition of a directed graph."""
    vertices = list(dict.fromkeys(vertices))  # stable order, no duplicates
    known = set(vertices)
    adj = defaultdict(list)
    radj = defaultdict(list)
    for u, v in edges:
        if u not in known or v not in known:
            raise ValueError("every edge endpoint must appear in vertices")
        adj[u].append(v)
        radj[v].append(u)

    # Pass 1: record finish order on G
    visited = set()
    finish_order = []

    def dfs1(u):
        visited.add(u)
        for v in adj[u]:
            if v not in visited:
                dfs1(v)
        finish_order.append(u)   # append on finish -> later entries finish later

    for v in vertices:
        if v not in visited:
            dfs1(v)

    # Pass 2: DFS on G^T in decreasing finish-time order
    visited.clear()
    sccs = []

    def dfs2(u, component):
        visited.add(u)
        component.append(u)
        for v in radj[u]:
            if v not in visited:
                dfs2(v, component)

    for v in reversed(finish_order):
        if v not in visited:
            component = []
            dfs2(v, component)
            sccs.append(component)

    return sccs

vertices = ["A", "B", "C", "D", "E"]
edges = [("A", "B"), ("B", "C"), ("C", "A"), ("C", "D"), ("D", "E"), ("E", "D")]

print(kosaraju_scc(vertices, edges))   # [['A', 'C', 'B'], ['D', 'E']]  (order may vary within each SCC)

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
using namespace std;

void dfs1(string u, unordered_map<string, vector<string>>& adj,
          unordered_set<string>& visited, vector<string>& finishOrder) {
    visited.insert(u);
    for (auto& v : adj[u]) if (!visited.count(v)) dfs1(v, adj, visited, finishOrder);
    finishOrder.push_back(u);
}

void dfs2(string u, unordered_map<string, vector<string>>& radj,
          unordered_set<string>& visited, vector<string>& component) {
    visited.insert(u);
    component.push_back(u);
    for (auto& v : radj[u]) if (!visited.count(v)) dfs2(v, radj, visited, component);
}

int main() {
    unordered_map<string, vector<string>> adj = {
        {"A", {"B"}}, {"B", {"C"}}, {"C", {"A", "D"}}, {"D", {"E"}}, {"E", {"D"}}
    };
    unordered_map<string, vector<string>> radj;
    for (auto& [u, list] : adj) for (auto& v : list) radj[v].push_back(u);

    vector<string> vertices = {"A", "B", "C", "D", "E"};
    unordered_set<string> visited;
    vector<string> finishOrder;
    for (auto& v : vertices) if (!visited.count(v)) dfs1(v, adj, visited, finishOrder);

    visited.clear();
    reverse(finishOrder.begin(), finishOrder.end());
    int sccCount = 0;
    for (auto& v : finishOrder) {
        if (!visited.count(v)) {
            vector<string> component;
            dfs2(v, radj, visited, component);
            sccCount++;
            cout << "SCC " << sccCount << ": ";
            for (auto& u : component) cout << u << ' ';
            cout << '\n';
        }
    }
    cout << "Number of SCCs: " << sccCount << endl;
    return 0;
}

import java.util.*;

class Kosaraju {
    static void dfs1(String u, Map<String, List<String>> adj, Set<String> visited, List<String> finishOrder) {
        visited.add(u);
        for (String v : adj.getOrDefault(u, List.of())) {
            if (!visited.contains(v)) dfs1(v, adj, visited, finishOrder);
        }
        finishOrder.add(u);
    }

    static void dfs2(String u, Map<String, List<String>> radj, Set<String> visited, List<String> component) {
        visited.add(u);
        component.add(u);
        for (String v : radj.getOrDefault(u, List.of())) {
            if (!visited.contains(v)) dfs2(v, radj, visited, component);
        }
    }

    public static void main(String[] args) {
        Map<String, List<String>> adj = new HashMap<>();
        adj.put("A", List.of("B")); adj.put("B", List.of("C"));
        adj.put("C", List.of("A", "D")); adj.put("D", List.of("E")); adj.put("E", List.of("D"));

        Map<String, List<String>> radj = new HashMap<>();
        for (var entry : adj.entrySet())
            for (String v : entry.getValue())
                radj.computeIfAbsent(v, k -> new ArrayList<>()).add(entry.getKey());

        List<String> vertices = List.of("A", "B", "C", "D", "E");
        Set<String> visited = new HashSet<>();
        List<String> finishOrder = new ArrayList<>();
        for (String v : vertices) if (!visited.contains(v)) dfs1(v, adj, visited, finishOrder);

        visited.clear();
        Collections.reverse(finishOrder);
        int sccCount = 0;
        for (String v : finishOrder) {
            if (!visited.contains(v)) {
                List<String> component = new ArrayList<>();
                dfs2(v, radj, visited, component);
                sccCount++;
                System.out.println("SCC " + sccCount + ": " + component);
            }
        }
        System.out.println("Number of SCCs: " + sccCount);
    }
}

Building the Condensation DAG

Once Pass 2 assigns a component ID comp[v] to every vertex, building the component graph is straightforward. For each original edge $u\to v$, add comp[u] → comp[v] when the IDs differ. Deduplicate repeated component pairs if downstream code expects a simple DAG.

With this article's convention—Pass 1 on $G$, Pass 2 on $G^T$—the SCCs are discovered from sources toward sinks in the original condensation DAG. That component order is therefore already a valid topological order, although vertex order inside each SCC remains arbitrary.

Real-World Applications

Kosaraju or Tarjan?

Pitfalls & Debugging

Exercises