Chapter 80

Home

Strongly Connected Components: Kosaraju

In a directed graph, an SCC is a maximal set of nodes where every node is reachable from every other node. Kosaraju's algorithm uses two DFS passes — one on the original graph, one on the reversed graph — to find all SCCs in O(V+E).

Kosaraju's Algorithm

(1) DFS on original graph, record finish order. (2) Reverse all edges. (3) Process nodes in reverse finish order, each DFS on the reversed graph finds one SCC.

C++ — Kosaraju

void dfs1(int u, vector>& adj, vector& vis, vector& order) {
    vis[u] = true;
    for (int v : adj[u]) if (!vis[v]) dfs1(v, adj, vis, order);
    order.push_back(u);
}

void dfs2(int u, vector>& radj, vector& comp, int id) {
    comp[u] = id;
    for (int v : radj[u]) if (comp[v] == -1) dfs2(v, radj, comp, id);
}

vector kosaraju(vector>& adj, int V) {
    vector vis(V, false);
    vector order;
    for (int i = 0; i < V; i++) if (!vis[i]) dfs1(i, adj, vis, order);

    // Reverse graph
    vector> radj(V);
    for (int u = 0; u < V; u++)
        for (int v : adj[u]) radj[v].push_back(u);

    vector comp(V, -1);
    int id = 0;
    for (int i = V - 1; i >= 0; i--)
        if (comp[order[i]] == -1)
            dfs2(order[i], radj, comp, id++);

    return comp;  // comp[u] = SCC id of node u
}

Rust — Kosaraju

fn kosaraju(adj: &[Vec]) -> Vec {
    let v = adj.len();
    let mut visited = vec![false; v];
    let mut order = Vec::new();

    fn dfs1(u: usize, adj: &[Vec], vis: &mut Vec, order: &mut Vec) {
        vis[u] = true;
        for &v in &adj[u] { if !vis[v] { dfs1(v, adj, vis, order); } }
        order.push(u);
    }

    for i in 0..v { if !visited[i] { dfs1(i, adj, &mut visited, &mut order); } }

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

    let mut comp = vec![-1; v];
    let mut id = 0;
    fn dfs2(u: usize, radj: &[Vec], comp: &mut Vec, id: i32) {
        comp[u] = id;
        for &v in &radj[u] { if comp[v] == -1 { dfs2(v, radj, comp, id); } }
    }

    for &u in order.iter().rev() {
        if comp[u] == -1 { dfs2(u, &radj, &mut comp, id); id += 1; }
    }
    comp
}

Key Takeaways