Strongly Connected Components (SCC) - Kosaraju's Algorithm

1. Introduction and Problem Statement

Strongly Connected Components (SCCs) are a fundamental graph theory concept that apply exclusively to directed graphs.

When tackling interview questions related to SCCs, you will typically encounter two primary variants:

• Count Queries: Figure out the total number of strongly connected components in the graph.
• Enumeration Queries: Print or return all the distinct SCCs separately.

Definition: A strongly connected component is a maximal subgraph of a directed graph where every vertex is reachable from every other vertex within that same subgraph. That is, for any pair of vertices $u$ and $v$ in an SCC, there exists a path from $u$ to $v$ and a path from $v$ to $u$.

2. Real-Life Mental Model & Intuition

Real-Life Analogy: Island Communities with One-Way Bridges

Imagine a map consisting of several island communities (SCCs). Within each island, roads run in both directions between all towns, meaning you can travel from Town A to Town B and back from Town B to Town A effortlessly.

However, the bridges between different islands are strictly one-way toll roads. You can drive from Island 1 to Island 2, and from Island 2 to Island 3, but you can never drive backward from Island 3 to Island 2.

If you start driving from a town in Island 1, because of the one-way bridges, you will eventually cascade through Island 1, cross over to Island 2, cascade through all its towns, cross over to Island 3, and visit the entire map. By simply launching a standard Depth-First Search (DFS) from Island 1, you end up visiting every single node across all islands. Consequently, a naive DFS cannot distinguish where one island ends and another begins.

3. The Core Challenge & The Brilliant Insight

If a standard DFS from the first component bleeds over into subsequent components due to directed edges, how do we isolate them?

• The Problem: Edges flow downstream from $\text{SCC}_1 \rightarrow \text{SCC}_2 \rightarrow \text{SCC}_3 \rightarrow \text{SCC}_4$. A naive traversal visits everything.
• The Insight: What if we reverse all the edges in the graph?
  • Reversing internal edges within an SCC doesn't destroy the SCC property because every node was already reachable from every other node.
  • However, reversing the inter-component bridges ($\text{SCC}_1 \leftarrow \text{SCC}_2$) traps our traversal. If we start a DFS inside $\text{SCC}_1$ on a reversed graph, we can explore $\text{SCC}_1$ fully, but we cannot leak into $\text{SCC}_2$ because the bridge now points backward!

4. Why We Need Finishing Times (The Ordering Dilemma)

If we reverse the graph and pick an arbitrary starting node, what if we accidentally picked a node inside $\text{SCC}_4$ instead of $\text{SCC}_1$? We would only explore $\text{SCC}_4$ and miss the rest.

We need to know which component comes first in the original directed flow so we can process them in the correct sequence. This is solved by tracking the finish time of vertices during a preliminary DFS.

5. Kosaraju's Algorithm: Step-by-Step Workflow

Kosaraju's Algorithm solves the SCC problem in three distinct steps:

Detailed Breakdown of the Three Steps:

1. Sort/Store by Finish Time (Step 1): Run a standard DFS across all unvisited nodes. When a node's recursive branch fully exhausts (it has nowhere else unvisited to go), push it onto a Stack. The node that finishes last ends up at the bottom of the stack, and the node that finishes first ends up at the top.
2. Reverse the Graph (Step 2): Create a transpose adjacency list (adjT). For every directed edge $u \to v$ in the original graph, insert an edge $v \to u$ in the transposed graph.
3. Process DFS in Stack Order (Step 3): Pop nodes one by one from the Stack. If the popped node is unvisited in the transposed graph, initiate a DFS from it. Every node reached during this traversal belongs to the exact same Strongly Connected Component.

6. Complete Implementation (Java & C++)

Java Implementation

import java.util.*;

class Solution {
    private void dfs(int node, int[] vis, ArrayList<ArrayList<Integer>> adj, Stack<Integer> st) {
        vis[node] = 1;
        for (int neighbor : adj.get(node)) {
            if (vis[neighbor] == 0) {
                dfs(neighbor, vis, adj, st);
            }
        }
        st.push(node);
    }

    private void dfs3(int node, int[] vis, ArrayList<ArrayList<Integer>> adjT) {
        vis[node] = 1;
        for (int neighbor : adjT.get(node)) {
            if (vis[neighbor] == 0) {
                dfs3(neighbor, vis, adjT);
            }
        }
    }

    public int kosaraju(int V, ArrayList<ArrayList<Integer>> adj) {
        int[] vis = new int[V];
        Stack<Integer> st = new Stack<>();
        
        // Step 1: Find finish times
        for (int i = 0; i < V; i++) {
            if (vis[i] == 0) {
                dfs(i, vis, adj, st);
            }
        }

        // Step 2: Reverse the graph (Transpose)
        ArrayList<ArrayList<Integer>> adjT = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adjT.add(new ArrayList<>());
        }
        for (int i = 0; i < V; i++) {
            for (int neighbor : adj.get(i)) {
                adjT.get(neighbor).add(i);
            }
        }

        // Step 3: Process DFS in order of stack finish times
        Arrays.fill(vis, 0);
        int sccCount = 0;
        
        while (!st.isEmpty()) {
            int node = st.pop();
            if (vis[node] == 0) {
                sccCount++;
                dfs3(node, vis, adjT);
            }
        }
        
        return sccCount;
    }
}

C++ Implementation

#include <bits/stdc++.h>
using class Solution {
private:
    void dfs(int node, vector<int>& vis, vector<vector<int>>& adj, stack<int>& st) {
        vis[node] = 1;
        for (auto neighbor : adj[node]) {
            if (!vis[neighbor]) {
                dfs(neighbor, vis, adj, st);
            }
        }
        st.push(node);
    }

    void dfs3(int node, vector<int>& vis, vector<vector<int>>& adjT) {
        vis[node] = 1;
        for (auto neighbor : adjT[node]) {
            if (!vis[neighbor]) {
                dfs3(neighbor, vis, adjT);
            }
        }
    }

public:
    int kosaraju(int V, vector<vector<int>>& adj) {
        vector<int> vis(V, 0);
        stack<int> st;
        
        // Step 1: Find finish times
        for (int i = 0; i < V; i++) {
            if (!vis[i]) {
                dfs(i, vis, adj, st);
            }
        }

        // Step 2: Reverse the graph (Transpose)
        vector<vector<int>> adjT(V);
        for (int i = 0; i < V; i++) {
            for (auto neighbor : adj[i]) {
                adjT[neighbor].push_back(i);
            }
        }

        // Step 3: Process DFS in order of stack finish times
        fill(vis.begin(), vis.end(), 0);
        int sccCount = 0;
        
        while (!st.empty()) {
            int node = st.top();
            st.pop();
            if (!vis[node]) {
                sccCount++;
                dfs3(node, vis, adjT);
            }
        }
        
        return sccCount;
    }
};

7. Complexity Analysis

8. Summary and Key Takeaways

• Strictly Directed: Strongly Connected Components are defined exclusively for directed graphs where every vertex in a component can reach every other vertex.
• The Core Roadblock: A standard DFS run on the original graph bleeds across components due to one-way directed edges between different SCCs.
• The Power of Reversing: Reversing graph edges traps traversals within their respective components because inter-component bridges point the wrong way.
• Finish Time Ordering: Utilizing a Stack to record node completion times ensures that we process components in the correct downstream order.
• Three-Step Execution: Kosaraju's algorithm is cleanly executed via: (1) Finish-time DFS into a Stack, (2) Graph transposition, and (3) Stack-ordered DFS on the transposed graph.
• Optimal Efficiency: The algorithm runs in linear time $O(V + E)$ by performing three sequential graph traversals.