804 Fundamental

804-tarjan-scc — Tarjan's Strongly Connected Components

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "804-tarjan-scc — Tarjan's Strongly Connected Components" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. A Strongly Connected Component (SCC) is a maximal subgraph where every vertex can reach every other vertex. Key difference from OCaml: 1. **Recursion vs iteration**: Recursive Tarjan's risks stack overflow on large graphs; Rust's implementation uses an explicit stack to avoid this; OCaml's `ulimit

Tutorial

The Problem

A Strongly Connected Component (SCC) is a maximal subgraph where every vertex can reach every other vertex. Tarjan's algorithm (1972) finds all SCCs in O(V+E) time using a single DFS, tracking discovery times and low-link values. SCCs are used in compiler optimization (detecting cycles in dataflow graphs), social network analysis (finding tight-knit communities), deadlock detection, and 2-SAT (satisfiability) solvers.

🎯 Learning Outcomes

• Track discovery time (disc) and low-link value (low) per vertex during DFS

• Use an explicit stack to track vertices that could form an SCC

• Identify SCC roots: vertices where low[v] == disc[v] after all descendants are processed

• Pop the SCC from the stack when a root is found

• Understand the difference between tree edges, back edges, and cross edges in the DFS

Code Example

#![allow(clippy::all)]
//! # Tarjan's SCC Algorithm

pub fn tarjan_scc(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> {
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
    }

    let mut index = 0;
    let mut indices = vec![None; n];
    let mut low = vec![0; n];
    let mut on_stack = vec![false; n];
    let mut stack = vec![];
    let mut sccs = vec![];

    fn dfs(
        v: usize,
        adj: &[Vec<usize>],
        index: &mut usize,
        indices: &mut [Option<usize>],
        low: &mut [usize],
        on_stack: &mut [bool],
        stack: &mut Vec<usize>,
        sccs: &mut Vec<Vec<usize>>,
    ) {
        indices[v] = Some(*index);
        low[v] = *index;
        *index += 1;
        stack.push(v);
        on_stack[v] = true;

        for &w in &adj[v] {
            if indices[w].is_none() {
                dfs(w, adj, index, indices, low, on_stack, stack, sccs);
                low[v] = low[v].min(low[w]);
            } else if on_stack[w] {
                low[v] = low[v].min(indices[w].unwrap());
            }
        }

        if indices[v] == Some(low[v]) {
            let mut scc = vec![];
            while let Some(w) = stack.pop() {
                on_stack[w] = false;
                scc.push(w);
                if w == v {
                    break;
                }
            }
            sccs.push(scc);
        }
    }

    for v in 0..n {
        if indices[v].is_none() {
            dfs(
                v,
                &adj,
                &mut index,
                &mut indices,
                &mut low,
                &mut on_stack,
                &mut stack,
                &mut sccs,
            );
        }
    }
    sccs
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_tarjan() {
        let edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3)];
        let sccs = tarjan_scc(6, &edges);
        assert_eq!(sccs.len(), 2);
    }
}

(* Tarjan's SCC — O(V+E) recursive DFS *)

let tarjan_scc adj n =
  let disc     = Array.make n (-1) in
  let low      = Array.make n 0 in
  let on_stack = Array.make n false in
  let stack    = ref [] in
  let timer    = ref 0 in
  let sccs     = ref [] in

  let rec dfs u =
    disc.(u) <- !timer;
    low.(u)  <- !timer;
    incr timer;
    stack    := u :: !stack;
    on_stack.(u) <- true;
    List.iter (fun v ->
      if disc.(v) = -1 then begin
        dfs v;
        low.(u) <- min low.(u) low.(v)
      end else if on_stack.(v) then
        low.(u) <- min low.(u) disc.(v)
    ) adj.(u);
    (* u is root of SCC *)
    if low.(u) = disc.(u) then begin
      let scc = ref [] in
      let cont = ref true in
      while !cont do
        match !stack with
        | [] -> cont := false
        | w :: rest ->
          stack := rest;
          on_stack.(w) <- false;
          scc := w :: !scc;
          if w = u then cont := false
      done;
      sccs := !scc :: !sccs
    end
  in
  for v = 0 to n - 1 do
    if disc.(v) = -1 then dfs v
  done;
  !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 = tarjan_scc adj n in
  Printf.printf "Number of SCCs: %d\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

Key Differences

Recursion vs iteration: Recursive Tarjan's risks stack overflow on large graphs; Rust's implementation uses an explicit stack to avoid this; OCaml's ulimit -s or Thread.create can work around the limit.

Mutable state: Tarjan's requires mutable arrays for disc, low, on_stack; both languages use mutable arrays directly.

Applications: 2-SAT solvers use Tarjan's SCC to check satisfiability in O(n+m) time; Rust constraint solvers use this pattern.

Condensation: The DAG of SCCs (the "condensation") has no cycles; computing it from Tarjan's output enables topological processing of cyclic graphs.

OCaml Approach

OCaml implements Tarjan's with ref cells for index_counter, on_stack: bool array, and stack: int list ref. Recursive DFS using let rec dfs v = ... is natural in OCaml. The Ocamlgraph library provides SCC.scc_list using Tarjan's or Kosaraju's algorithm. OCaml's exception mechanism can implement the "pop until root" with cleaner control flow.

Full Source

#![allow(clippy::all)]
//! # Tarjan's SCC Algorithm

pub fn tarjan_scc(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> {
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
    }

    let mut index = 0;
    let mut indices = vec![None; n];
    let mut low = vec![0; n];
    let mut on_stack = vec![false; n];
    let mut stack = vec![];
    let mut sccs = vec![];

    fn dfs(
        v: usize,
        adj: &[Vec<usize>],
        index: &mut usize,
        indices: &mut [Option<usize>],
        low: &mut [usize],
        on_stack: &mut [bool],
        stack: &mut Vec<usize>,
        sccs: &mut Vec<Vec<usize>>,
    ) {
        indices[v] = Some(*index);
        low[v] = *index;
        *index += 1;
        stack.push(v);
        on_stack[v] = true;

        for &w in &adj[v] {
            if indices[w].is_none() {
                dfs(w, adj, index, indices, low, on_stack, stack, sccs);
                low[v] = low[v].min(low[w]);
            } else if on_stack[w] {
                low[v] = low[v].min(indices[w].unwrap());
            }
        }

        if indices[v] == Some(low[v]) {
            let mut scc = vec![];
            while let Some(w) = stack.pop() {
                on_stack[w] = false;
                scc.push(w);
                if w == v {
                    break;
                }
            }
            sccs.push(scc);
        }
    }

    for v in 0..n {
        if indices[v].is_none() {
            dfs(
                v,
                &adj,
                &mut index,
                &mut indices,
                &mut low,
                &mut on_stack,
                &mut stack,
                &mut sccs,
            );
        }
    }
    sccs
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_tarjan() {
        let edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3)];
        let sccs = tarjan_scc(6, &edges);
        assert_eq!(sccs.len(), 2);
    }
}

(* Tarjan's SCC — O(V+E) recursive DFS *)

let tarjan_scc adj n =
  let disc     = Array.make n (-1) in
  let low      = Array.make n 0 in
  let on_stack = Array.make n false in
  let stack    = ref [] in
  let timer    = ref 0 in
  let sccs     = ref [] in

  let rec dfs u =
    disc.(u) <- !timer;
    low.(u)  <- !timer;
    incr timer;
    stack    := u :: !stack;
    on_stack.(u) <- true;
    List.iter (fun v ->
      if disc.(v) = -1 then begin
        dfs v;
        low.(u) <- min low.(u) low.(v)
      end else if on_stack.(v) then
        low.(u) <- min low.(u) disc.(v)
    ) adj.(u);
    (* u is root of SCC *)
    if low.(u) = disc.(u) then begin
      let scc = ref [] in
      let cont = ref true in
      while !cont do
        match !stack with
        | [] -> cont := false
        | w :: rest ->
          stack := rest;
          on_stack.(w) <- false;
          scc := w :: !scc;
          if w = u then cont := false
      done;
      sccs := !scc :: !sccs
    end
  in
  for v = 0 to n - 1 do
    if disc.(v) = -1 then dfs v
  done;
  !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 = tarjan_scc adj n in
  Printf.printf "Number of SCCs: %d\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

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_tarjan() {
        let edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3)];
        let sccs = tarjan_scc(6, &edges);
        assert_eq!(sccs.len(), 2);
    }
}

Deep Comparison

OCaml vs Rust: Tarjan Scc

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement the SCC condensation: build a DAG where each node is an SCC and edges represent inter-SCC connections. Verify it is a DAG.

Use SCCs to solve 2-SAT: given a 2-CNF formula, check satisfiability using Tarjan's and compute a satisfying assignment if one exists.

Detect and report all cycles in a directed graph using the SCCs: any SCC of size > 1 or any SCC containing a self-loop is a cycle.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust