Chapter 81

Home

Refactoring: Tarjan's SCC

Kosaraju needs two DFS passes and a reversed graph. Tarjan's algorithm finds SCCs in a single DFS pass using a stack and low-link values — no graph reversal needed.

Before: Kosaraju (Two Passes + Reverse Graph)

C++

// Pass 1: DFS for finish order
// Build reversed graph
// Pass 2: DFS on reversed graph
// Two data structures, two passes, more memory

After: Tarjan (Single Pass)

C++ — Tarjan's SCC

vector disc, low, comp;
vector on_stack;
stack st;
int timer = 0, scc_id = 0;

void tarjan_dfs(int u, vector>& adj) {
    disc[u] = low[u] = ++timer;
    st.push(u);
    on_stack[u] = true;

    for (int v : adj[u]) {
        if (disc[v] == 0) {              // tree edge
            tarjan_dfs(v, adj);
            low[u] = min(low[u], low[v]);
        } else if (on_stack[v]) {        // back edge
            low[u] = min(low[u], disc[v]);
        }
    }

    if (low[u] == disc[u]) {             // root of SCC
        while (true) {
            int v = st.top(); st.pop();
            on_stack[v] = false;
            comp[v] = scc_id;
            if (v == u) break;
        }
        scc_id++;
    }
}

// Single DFS, no reversed graph needed
// Also O(V+E)

Rust — Tarjan's SCC

fn tarjan(adj: &[Vec]) -> Vec {
    let n = adj.len();
    let mut disc = vec![0; n];
    let mut low = vec![0; n];
    let mut on_stack = vec![false; n];
    let mut comp = vec![-1; n];
    let mut st: Vec = Vec::new();
    let mut timer = 0;
    let mut scc_id = 0;

    fn dfs(u: usize, adj: &[Vec], disc: &mut Vec, low: &mut Vec,
           on_stack: &mut Vec, st: &mut Vec,
           timer: &mut i32, scc_id: &mut i32, comp: &mut Vec) {
        *timer += 1;
        disc[u] = *timer; low[u] = *timer;
        st.push(u); on_stack[u] = true;
        for &v in &adj[u] {
            if disc[v] == 0 {
                dfs(v, adj, disc, low, on_stack, st, timer, scc_id, comp);
                low[u] = low[u].min(low[v]);
            } else if on_stack[v] {
                low[u] = low[u].min(disc[v]);
            }
        }
        if low[u] == disc[u] {
            loop {
                let v = st.pop().unwrap();
                on_stack[v] = false;
                comp[v] = *scc_id;
                if v == u { break; }
            }
            *scc_id += 1;
        }
    }

    for i in 0..n { if disc[i] == 0 {
        dfs(i, adj, &mut disc, &mut low, &mut on_stack, &mut st, &mut timer, &mut scc_id, &mut comp);
    }}
    comp
}

💡 Tarjan vs Kosaraju

Both are O(V+E). Tarjan is a single DFS pass — no reversed graph, less memory. Kosaraju is easier to understand and remember. In contests, use whichever you're more confident debugging.

Key Takeaways