Graphs

Graph Patterns: Strongly Connected Components (Kosaraju's)

May 2026

8 min read

In directed graphs, just because A can reach B does not mean B can reach A. Kosaraju's Algorithm allows us to find exact clusters where all nodes have mutual reachability.

Introduction

A Strongly Connected Component (SCC) is a portion of a directed graph where there is a valid path from every vertex to every other vertex within that component.

Kosaraju's Two-Pass Algorithm

Kosaraju's algorithm is elegant and strictly structural.

Step 1: We perform a standard DFS on the graph. When a recursive call finishes (hits a dead end), we push that node onto a Stack. This orders the nodes by their "finishing time".

Step 2: We create a transpose of the graph. We literally reverse the direction of every single edge.

Step 3: We pop nodes off the Stack one by one and run DFS on the reversed graph. Because the edges are reversed, the DFS is physically trapped inside its Strongly Connected Component and cannot leak into other clusters. Every time a new DFS is launched from the Stack, a new SCC is counted.

Implementation

java

class Solution {
    public int kosaraju(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] vis = new boolean[V];
        Stack<Integer> st = new Stack<>();
        
        // Step 1: Sort nodes by finishing time
        for (int i = 0; i < V; i++) {
            if (!vis[i]) dfs1(i, vis, adj, st);
        }
        
        // Step 2: Reverse the graph edges
        ArrayList<ArrayList<Integer>> revAdj = new ArrayList<>();
        for (int i = 0; i < V; i++) revAdj.add(new ArrayList<>());
        for (int i = 0; i < V; i++) {
            vis[i] = false; // Reset visited array
            for (int neighbor : adj.get(i)) {
                revAdj.get(neighbor).add(i);
            }
        }
        
        // Step 3: DFS on reversed graph in stack order
        int sccCount = 0;
        while (!st.isEmpty()) {
            int node = st.pop();
            if (!vis[node]) {
                sccCount++;
                dfs2(node, vis, revAdj);
            }
        }
        return sccCount;
    }
    
    private void dfs1(int node, boolean[] vis, ArrayList<ArrayList<Integer>> adj, Stack<Integer> st) {
        vis[node] = true;
        for (int neighbor : adj.get(node)) {
            if (!vis[neighbor]) dfs1(neighbor, vis, adj, st);
        }
        st.push(node); // Push on finish
    }
    
    private void dfs2(int node, boolean[] vis, ArrayList<ArrayList<Integer>> revAdj) {
        vis[node] = true;
        for (int neighbor : revAdj.get(node)) {
            if (!vis[neighbor]) dfs2(neighbor, vis, revAdj);
        }
    }
}