805: Kosaraju's Two-Pass SCC Algorithm

Difficulty: 5 Level: Master Find all strongly connected components in a directed graph using two iterative DFS passes in O(V+E).

The Problem This Solves

A strongly connected component (SCC) is a maximal set of vertices such that every vertex is reachable from every other vertex in the set. SCCs partition any directed graph into clusters of mutual reachability — the building blocks of dependency analysis, deadlock detection, and compiler data-flow. Use Kosaraju's algorithm when you need to decompose a directed graph into its SCCs, condense it into a DAG, or analyze cyclic dependencies. It applies directly to module dependency graphs (finding circular imports), web link analysis (finding clusters of mutually-linked pages), and program analysis (detecting loops and reachable code). The output is a list of SCCs, each containing the vertex indices belonging to that component. After condensation, the resulting DAG gives you a topological order over the component structure.

The Intuition

The core insight: finish order in DFS reveals the SCC structure. In a DFS of the original graph, a vertex in a "sink" SCC (no outgoing cross-SCC edges) finishes last. If you then DFS the transposed graph starting from the highest-finish-order vertex, you stay within that SCC — because the transposed edges can't escape it. Two passes: 1. Pass 1 on original graph: run DFS, push each vertex to a stack on finish. Stack top = vertex that finished last. 2. Pass 2 on reversed graph: pop from stack, DFS from each unvisited vertex. Each DFS tree = one SCC. Time: O(V+E). Space: O(V+E) for the reversed adjacency list. In OCaml you'd use recursive DFS naturally. In Rust, recursion risks stack overflow on large graphs, so iterative DFS with an explicit stack and a `returning` flag to distinguish pre/post-visit is the idiomatic approach.

How It Works in Rust

fn kosaraju(adj: &[Vec<usize>]) -> Vec<Vec<usize>> {
 let n = adj.len();
 let mut visited = vec![false; n];
 let mut order = Vec::with_capacity(n); // finish order

 // Pass 1: iterative DFS on original graph, collect finish order
 for start in 0..n {
     if visited[start] { continue; }
     let mut stack = vec![(start, false)]; // (node, returning)
     while let Some((v, ret)) = stack.pop() {
         if ret {
             order.push(v); // finished — push to order
             continue;
         }
         if visited[v] { continue; }
         visited[v] = true;
         stack.push((v, true)); // push return marker
         for &w in &adj[v] {
             if !visited[w] { stack.push((w, false)); }
         }
     }
 }

 // Build reversed graph
 let mut radj = vec![vec![]; n];
 for v in 0..n {
     for &w in &adj[v] { radj[w].push(v); }
 }

 // Pass 2: DFS on reversed graph in reverse finish order
 let mut comp = vec![usize::MAX; n];
 let mut sccs: Vec<Vec<usize>> = Vec::new();
 let mut visited2 = vec![false; n];

 for start in order.into_iter().rev() {
     if visited2[start] { continue; }
     let scc_id = sccs.len();
     sccs.push(vec![]);
     let mut stack = vec![start];
     while let Some(v) = stack.pop() {
         if visited2[v] { continue; }
         visited2[v] = true;
         comp[v] = scc_id;
         sccs[scc_id].push(v);
         for &w in &radj[v] {
             if !visited2[w] { stack.push(w); }
         }
     }
 }
 sccs
}

Key Rust detail: the `(node, returning)` tuple in the stack replaces the implicit call-stack frame that recursive DFS uses. When `returning = true`, the node has been fully explored — equivalent to code after the recursive call returns.

What This Unlocks

Circular dependency detection in build systems, package managers, and module graphs — each SCC with >1 node is a cycle.
DAG condensation for topological scheduling: condense SCCs into single nodes, then topo-sort the resulting DAG.
2-SAT solving: SCCs in the implication graph directly encode satisfiability — a variable and its negation in the same SCC means UNSAT.

Key Differences

Concept	OCaml	Rust
DFS implementation	Natural recursion (risk: stack overflow on large graphs)	Iterative with explicit `(node, returning)` stack
Visited tracking	`Hashtbl` or mutable array via `ref`	`vec![false; n]` — direct indexed access
Graph representation	`Array.make n []` with `List` adjacency	`Vec<Vec<usize>>` — owned, cache-friendly
Reversed graph	Functional map/fold to build transpose	Imperative loop building `radj: Vec<Vec<usize>>`
SCC output	List of lists	`Vec<Vec<usize>>` with component id array

// Kosaraju's SCC — two iterative DFS passes, O(V+E)

fn kosaraju(adj: &[Vec<usize>]) -> Vec<Vec<usize>> {
    let n = adj.len();

    // Pass 1: DFS on original, record finish order
    let mut visited = vec![false; n];
    let mut finish  = Vec::new();
    for start in 0..n {
        if visited[start] { continue; }
        let mut stack = vec![(start, 0usize)];
        visited[start] = true;
        while let Some((u, idx)) = stack.last_mut() {
            let u = *u;
            if *idx < adj[u].len() {
                let v = adj[u][*idx]; *idx += 1;
                if !visited[v] { visited[v] = true; stack.push((v, 0)); }
            } else {
                finish.push(u);
                stack.pop();
            }
        }
    }

    // Build transposed graph
    let mut radj = vec![vec![]; n];
    for u in 0..n {
        for &v in &adj[u] { radj[v].push(u); }
    }

    // Pass 2: DFS on transposed in reverse finish order
    let mut visited2 = vec![false; n];
    let mut sccs = Vec::new();
    for &start in finish.iter().rev() {
        if visited2[start] { continue; }
        let mut scc   = Vec::new();
        let mut stack = vec![start];
        visited2[start] = true;
        while let Some(u) = stack.pop() {
            scc.push(u);
            for &v in &radj[u] {
                if !visited2[v] { visited2[v] = true; stack.push(v); }
            }
        }
        sccs.push(scc);
    }
    sccs
}

fn main() {
    let n = 8;
    let mut adj = vec![vec![]; n];
    let mut add = |u: usize, v: usize| adj[u].push(v);
    add(0,1); add(1,2); add(2,0); add(2,3);
    add(3,4); add(4,5); add(5,3);
    add(6,5); add(6,7); add(7,6);

    let sccs = kosaraju(&adj);
    println!("SCCs ({} total):", sccs.len());
    for (i, scc) in sccs.iter().enumerate() {
        println!("  SCC {}: {:?}", i + 1, scc);
    }
}

(* Kosaraju's SCC — two-pass DFS, O(V+E) *)

let kosaraju adj n =
  let visited = Array.make n false in
  let finish  = ref [] in  (* finish-time stack *)

  (* Pass 1: DFS on original graph, record finish order *)
  let rec dfs1 u =
    if not visited.(u) then begin
      visited.(u) <- true;
      List.iter dfs1 adj.(u);
      finish := u :: !finish
    end
  in
  for v = 0 to n - 1 do dfs1 v done;

  (* Build transposed graph *)
  let radj = Array.make n [] in
  for u = 0 to n - 1 do
    List.iter (fun v -> radj.(v) <- u :: radj.(v)) adj.(u)
  done;

  (* Pass 2: DFS on transposed graph in reverse finish order *)
  let visited2 = Array.make n false in
  let sccs     = ref [] in

  let rec dfs2 u scc =
    if not visited2.(u) then begin
      visited2.(u) <- true;
      let scc' = u :: scc in
      List.fold_left (fun acc v -> dfs2 v acc) scc' radj.(u)
    end else scc
  in
  List.iter (fun u ->
    if not visited2.(u) then
      sccs := List.sort compare (dfs2 u []) :: !sccs
  ) !finish;
  !sccs

let () =
  let n   = 8 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u) in
  add 0 1; add 1 2; add 2 0; add 2 3;
  add 3 4; add 4 5; add 5 3;
  add 6 5; add 6 7; add 7 6;
  let sccs = kosaraju adj n in
  Printf.printf "SCCs (%d total):\n" (List.length sccs);
  List.iteri (fun i scc ->
    Printf.printf "  SCC %d: [%s]\n" (i+1)
      (String.concat "," (List.map string_of_int scc))
  ) sccs