ProgramGuru

Strongly Connected Components using Kosaraju's Algorithm

Problem and examples

Given a directed graph with V vertices (numbered from 0 to V - 1) and E directed edges, your task is to find the number of Strongly Connected Components (SCCs).

A strongly connected component is a maximal group of vertices such that every vertex is reachable from every other vertex in the group via directed paths.

Graph (Adjacency List) Vertices Edges Output Description
{ 0: [1], 1: [2], 2: [0], 3: [4] } 5 [(0→1), (1→2), (2→0), (3→4)] 2 Two SCCs: {0,1,2} and {3,4}
{ 0: [1], 1: [2], 2: [3], 3: [] } 4 [(0→1), (1→2), (2→3)] 4 No cycles, each node is its own SCC
{} 0 [] 0 Empty graph has no components
{ 0: [0] } 1 [(0→0)] 1 Self loop is a valid SCC
{ 0: [1], 1: [2], 2: [0], 3: [2,4], 4: [3] } 5 [(0→1), (1→2), (2→0), (3→2), (3→4), (4→3)] 2 {0,1,2} and {3,4} are two SCCs

How it works

Understanding the Problem

In a directed graph, a Strongly Connected Component (SCC) is a group of vertices where every vertex is reachable from every other vertex in that group. In simpler terms, if you can start at any node in the group and reach all the others through the directed edges—and also get back to the starting node—then those nodes form an SCC.

Our goal is to identify all such strongly connected components in a given directed graph. We'll solve this using Kosaraju's Algorithm, which is efficient and beginner-friendly once understood step-by-step.

Step-by-Step Solution with Example

Step 1: Do a DFS on the original graph and record finish times

Start by doing a standard DFS traversal of the graph. As we finish exploring each node (i.e., all its neighbors are visited), we push it onto a stack. This stack captures the nodes in the order of their finishing times—the last finished node ends up on top.

Why? This helps us process nodes in the right order during the second DFS on the transposed graph.

Step 2: Transpose the graph (reverse all edges)

Next, we reverse all the directed edges in the graph. That is, if there was an edge from A → B, in the transposed graph it becomes B → A.

This reversal helps us discover which nodes can be reached in reverse direction, a key aspect in identifying SCCs.

Step 3: Do DFS on the transposed graph using the stack order

Now, we pop nodes one by one from the stack and perform DFS on the transposed graph. Each time we start a new DFS from an unvisited node, we find one SCC—all the nodes reached in this DFS form a strongly connected component.

Since the stack ensures we process nodes in decreasing order of finish times, we are guaranteed that whenever we start a new DFS, we start from a root node of some SCC.

Example: Step-by-step on a sample graph


Graph:
Vertices = {0, 1, 2, 3, 4}
Edges = {
  0 → 2,
  2 → 1,
  1 → 0,
  0 → 3,
  3 → 4
}

Step 1: DFS Finish Order (pushed to stack): [4, 3, 0, 1, 2]
Step 2: Transpose Graph:
  2 → 0
  1 → 2
  0 → 1
  3 → 0
  4 → 3

Step 3: DFS on Transposed Graph in Stack Order:
- Start DFS from 2 → reaches 2, 1, 0 → SCC1 = [2,1,0]
- Next node in stack is 1 → already visited
- Next is 0 → already visited
- Next is 3 → reaches 3 → SCC2 = [3]
- Next is 4 → reaches 4 → SCC3 = [4]

Final SCCs: [2,1,0], [3], [4]

Edge Cases

  • Empty Graph: No vertices means no SCCs to find.
  • Single Node: A single node with or without a self-loop is an SCC by itself.
  • Disconnected Nodes: Nodes with no outgoing or incoming edges form their own SCCs.
  • Multiple Cycles: Kosaraju's algorithm naturally groups cycles correctly into separate SCCs.

Finally

Kosaraju’s Algorithm is a powerful and intuitive method to identify strongly connected components. Its beauty lies in the simplicity of using two DFS traversals—first to record finish order, and second to explore reversed connectivity.

It runs in linear time O(V + E), making it suitable even for large graphs. As you work through the steps, always remember that SCCs are about mutual reachability, and DFS with finish order is the key to unlocking that structure.

  1. Initialize a visited array and an empty stack.
  2. For each unvisited vertex, perform DFS and push the vertex onto the stack after visiting all its descendants.
  3. Reverse all edges of the graph (create a transpose).
  4. Reset the visited array.
  5. While the stack is not empty:
    1. Pop a vertex from the stack.
    2. If it hasn't been visited, perform DFS from that node in the transposed graph.
    3. Each such DFS traversal gives one strongly connected component.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// Graph adjacency list node
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// Graph structure
typedef struct Graph {
    int numVertices;
    Node* adjLists[MAX_VERTICES];
    int visited[MAX_VERTICES];
} Graph;

Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

void dfs(Graph* graph, int vertex, int* stack, int* stackIndex) {
    graph->visited[vertex] = 1;
    Node* temp = graph->adjLists[vertex];
    while (temp) {
        int adjVertex = temp->vertex;
        if (!graph->visited[adjVertex]) {
            dfs(graph, adjVertex, stack, stackIndex);
        }
        temp = temp->next;
    }
    stack[(*stackIndex)++] = vertex;
}

void dfsTranspose(Graph* graph, int vertex, int* visited) {
    visited[vertex] = 1;
    Node* temp = graph->adjLists[vertex];
    while (temp) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            dfsTranspose(graph, adjVertex, visited);
        }
        temp = temp->next;
    }
}

Graph* getTranspose(Graph* graph) {
    Graph* gT = createGraph(graph->numVertices);
    for (int v = 0; v < graph->numVertices; v++) {
        Node* temp = graph->adjLists[v];
        while (temp) {
            addEdge(gT, temp->vertex, v);
            temp = temp->next;
        }
    }
    return gT;
}

int kosarajuSCC(Graph* graph) {
    int stack[MAX_VERTICES];
    int stackIndex = 0;

    for (int i = 0; i < graph->numVertices; i++) {
        if (!graph->visited[i]) {
            dfs(graph, i, stack, &stackIndex);
        }
    }

    Graph* transposeGraph = getTranspose(graph);
    int visited[MAX_VERTICES] = {0};
    int count = 0;

    for (int i = stackIndex - 1; i >= 0; i--) {
        int v = stack[i];
        if (!visited[v]) {
            dfsTranspose(transposeGraph, v, visited);
            count++;
        }
    }

    return count;
}

int main() {
    int V = 5;
    Graph* graph = createGraph(V);

    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 3, 4);

    int sccCount = kosarajuSCC(graph);
    printf("Number of Strongly Connected Components: %d\n", sccCount);

    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Graph {
    int V;
    vector<vector<int>> adj;
public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    void dfs(int v, vector<bool>& visited, stack<int>& Stack) {
        visited[v] = true;
        for (int u : adj[v]) {
            if (!visited[u]) dfs(u, visited, Stack);
        }
        Stack.push(v);
    }

    void dfsTranspose(int v, vector<bool>& visited, vector<vector<int>>& transposeAdj) {
        visited[v] = true;
        for (int u : transposeAdj[v]) {
            if (!visited[u]) dfsTranspose(u, visited, transposeAdj);
        }
    }

    int kosarajuSCC() {
        stack<int> Stack;
        vector<bool> visited(V, false);

        for (int i = 0; i < V; i++) {
            if (!visited[i]) dfs(i, visited, Stack);
        }

        vector<vector<int>> transposeAdj(V);
        for (int i = 0; i < V; i++) {
            for (int u : adj[i]) {
                transposeAdj[u].push_back(i);
            }
        }

        fill(visited.begin(), visited.end(), false);
        int count = 0;

        while (!Stack.empty()) {
            int v = Stack.top();
            Stack.pop();

            if (!visited[v]) {
                dfsTranspose(v, visited, transposeAdj);
                count++;
            }
        }

        return count;
    }
};

int main() {
    int V = 5;
    Graph graph(V);
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(2, 0);
    graph.addEdge(3, 4);

    cout << "Number of Strongly Connected Components: " << graph.kosarajuSCC() << endl;
    return 0;
}

Python implementation

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def dfs(self, v, visited, stack):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                self.dfs(i, visited, stack)
        stack.append(v)

    def transpose(self):
        g = Graph(self.V)
        for u in self.graph:
            for v in self.graph[u]:
                g.add_edge(v, u)
        return g

    def dfs_transpose(self, v, visited):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                self.dfs_transpose(i, visited)

    def kosaraju_scc(self):
        visited = [False] * self.V
        stack = []

        for i in range(self.V):
            if not visited[i]:
                self.dfs(i, visited, stack)

        gr = self.transpose()
        visited = [False] * self.V

        count = 0
        while stack:
            v = stack.pop()
            if not visited[v]:
                gr.dfs_transpose(v, visited)
                count += 1

        return count

if __name__ == "__main__":
    g = Graph(5)
    g.add_edge(0, 1)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(3, 4)
    print("Number of Strongly Connected Components:", g.kosaraju_scc())

Java implementation

import java.util.*;

public class KosarajuSCC {

    private int V;
    private List<List<Integer>> adj;

    public KosarajuSCC(int V) {
        this.V = V;
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adj.get(u).add(v);
    }

    private void dfs(int v, boolean[] visited, Stack<Integer> stack) {
        visited[v] = true;
        for (int u : adj.get(v)) {
            if (!visited[u]) dfs(u, visited, stack);
        }
        stack.push(v);
    }

    private void dfsTranspose(int v, boolean[] visited, List<List<Integer>> transposeAdj) {
        visited[v] = true;
        for (int u : transposeAdj.get(v)) {
            if (!visited[u]) dfsTranspose(u, visited, transposeAdj);
        }
    }

    private List<List<Integer>> getTranspose() {
        List<List<Integer>> transposeAdj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            transposeAdj.add(new ArrayList<>());
        }

        for (int v = 0; v < V; v++) {
            for (int u : adj.get(v)) {
                transposeAdj.get(u).add(v);
            }
        }
        return transposeAdj;
    }

    public int kosarajuSCC() {
        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < V; i++) {
            if (!visited[i]) dfs(i, visited, stack);
        }

        List<List<Integer>> transposeAdj = getTranspose();
        Arrays.fill(visited, false);

        int count = 0;
        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (!visited[v]) {
                dfsTranspose(v, visited, transposeAdj);
                count++;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        KosarajuSCC graph = new KosarajuSCC(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(3, 4);

        System.out.println("Number of Strongly Connected Components: " + graph.kosarajuSCC());
    }
}

JavaScript implementation

function kosarajuSCC(V, adj) {
  const visited = new Array(V).fill(false);
  const stack = [];

  function dfs(v) {
    visited[v] = true;
    for (let nei of adj[v] || []) {
      if (!visited[nei]) dfs(nei);
    }
    stack.push(v);
  }

  for (let i = 0; i < V; i++) {
    if (!visited[i]) dfs(i);
  }

  const transpose = Array.from({ length: V }, () => []);
  for (let u = 0; u < V; u++) {
    for (let v of adj[u] || []) {
      transpose[v].push(u);
    }
  }

  visited.fill(false);
  let count = 0;

  function reverseDFS(v) {
    visited[v] = true;
    for (let nei of transpose[v]) {
      if (!visited[nei]) reverseDFS(nei);
    }
  }

  while (stack.length > 0) {
    const node = stack.pop();
    if (!visited[node]) {
      reverseDFS(node);
      count++;
    }
  }

  return count;
}

// Example usage
const graph = {
  0: [1],
  1: [2],
  2: [0],
  3: [4]
};

console.log("Number of Strongly Connected Components:", kosarajuSCC(5, graph));

Go implementation

package main

import "fmt"

func dfs(v int, visited []bool, adj [][]int, stack *[]int) {
    visited[v] = true
    for _, u := range adj[v] {
        if !visited[u] {
            dfs(u, visited, adj, stack)
        }
    }
    *stack = append(*stack, v)
}

func dfsTranspose(v int, visited []bool, transpose [][]int) {
    visited[v] = true
    for _, u := range transpose[v] {
        if !visited[u] {
            dfsTranspose(u, visited, transpose)
        }
    }
}

func getTranspose(V int, adj [][]int) [][]int {
    transpose := make([][]int, V)
    for i := 0; i < V; i++ {
        transpose[i] = []int{}
    }

    for u := 0; u < V; u++ {
        for _, v := range adj[u] {
            transpose[v] = append(transpose[v], u)
        }
    }
    return transpose
}

func kosarajuSCC(V int, adj [][]int) int {
    visited := make([]bool, V)
    var stack []int

    for i := 0; i < V; i++ {
        if !visited[i] {
            dfs(i, visited, adj, &stack)
        }
    }

    transpose := getTranspose(V, adj)
    for i := range visited {
        visited[i] = false
    }

    count := 0
    for i := len(stack) - 1; i >= 0; i-- {
        v := stack[i]
        if !visited[v] {
            dfsTranspose(v, visited, transpose)
            count++
        }
    }
    return count
}

func main() {
    V := 5
    adj := make([][]int, V)
    adj[0] = []int{1}
    adj[1] = []int{2}
    adj[2] = []int{0}
    adj[3] = []int{4}

    sccCount := kosarajuSCC(V, adj)
    fmt.Printf("Number of Strongly Connected Components: %d\n", sccCount)
}

Rust implementation

use std::collections::VecDeque;

fn dfs(v: usize, visited: &mut Vec<bool>, adj: &Vec<Vec<usize>>, stack: &mut Vec<usize>) {
    visited[v] = true;
    for &u in &adj[v] {
        if !visited[u] {
            dfs(u, visited, adj, stack);
        }
    }
    stack.push(v);
}

fn dfs_transpose(v: usize, visited: &mut Vec<bool>, transpose: &Vec<Vec<usize>>) {
    visited[v] = true;
    for &u in &transpose[v] {
        if !visited[u] {
            dfs_transpose(u, visited, transpose);
        }
    }
}

fn get_transpose(V: usize, adj: &Vec<Vec<usize>>) -> Vec<Vec<usize>> {
    let mut transpose = vec![vec![]; V];
    for u in 0..V {
        for &v in &adj[u] {
            transpose[v].push(u);
        }
    }
    transpose
}

fn kosaraju_scc(V: usize, adj: Vec<Vec<usize>>) -> usize {
    let mut visited = vec![false; V];
    let mut stack = Vec::new();

    for i in 0..V {
        if !visited[i] {
            dfs(i, &mut visited, &adj, &mut stack);
        }
    }

    let transpose = get_transpose(V, &adj);
    visited.fill(false);

    let mut count = 0;

    while let Some(v) = stack.pop() {
        if !visited[v] {
            dfs_transpose(v, &mut visited, &transpose);
            count += 1;
        }
    }
    count
}

fn main() {
    let V = 5;
    let adj = vec![
        vec![1],
        vec![2],
        vec![0],
        vec![4],
        vec![],
    ];

    let scc_count = kosaraju_scc(V, adj);
    println!("Number of Strongly Connected Components: {}", scc_count);
}

Kotlin implementation

fun main() {
    val V = 5
    val adj = Array(V) { mutableListOf<Int>() }

    adj[0].add(1)
    adj[1].add(2)
    adj[2].add(0)
    adj[3].add(4)

    val visited = BooleanArray(V) { false }
    val stack = mutableListOf<Int>()

    fun dfs(v: Int) {
        visited[v] = true
        for (u in adj[v]) {
            if (!visited[u]) dfs(u)
        }
        stack.add(v)
    }

    for (i in 0 until V) {
        if (!visited[i]) dfs(i)
    }

    val transpose = Array(V) { mutableListOf<Int>() }
    for (u in 0 until V) {
        for (v in adj[u]) {
            transpose[v].add(u)
        }
    }

    visited.fill(false)

    fun dfsTranspose(v: Int) {
        visited[v] = true
        for (u in transpose[v]) {
            if (!visited[u]) dfsTranspose(u)
        }
    }

    var count = 0
    while (stack.isNotEmpty()) {
        val v = stack.removeAt(stack.size - 1)
        if (!visited[v]) {
            dfsTranspose(v)
            count++
        }
    }

    println("Number of Strongly Connected Components: $count")
}

Swift implementation

import Foundation

func dfs(_ v: Int, _ visited: inout [Bool], _ adj: [[Int]], _ stack: inout [Int]) {
    visited[v] = true
    for u in adj[v] {
        if !visited[u] {
            dfs(u, &visited, adj, &stack)
        }
    }
    stack.append(v)
}

func dfsTranspose(_ v: Int, _ visited: inout [Bool], _ transpose: [[Int]]) {
    visited[v] = true
    for u in transpose[v] {
        if !visited[u] {
            dfsTranspose(u, &visited, transpose)
        }
    }
}

func getTranspose(_ V: Int, _ adj: [[Int]]) -> [[Int]] {
    var transpose = Array(repeating: [Int](), count: V)
    for u in 0 ..< V {
        for v in adj[u] {
            transpose[v].append(u)
        }
    }
    return transpose
}

func kosarajuSCC(_ V: Int, _ adj: [[Int]]) -> Int {
    var visited = Array(repeating: false, count: V)
    var stack = [Int]()

    for i in 0 ..< V {
        if !visited[i] {
            dfs(i, &visited, adj, &stack)
        }
    }

    let transpose = getTranspose(V, adj)
    visited = Array(repeating: false, count: V)

    var count = 0
    while !stack.isEmpty {
        let v = stack.removeLast()
        if !visited[v] {
            dfsTranspose(v, &visited, transpose)
            count += 1
        }
    }
    return count
}

let V = 5
let adj = [
    [1],
    [2],
    [0],
    [4],
    []
]

let sccCount = kosarajuSCC(V, adj)
print("Number of Strongly Connected Components: \(sccCount)")

TypeScript implementation

function kosarajuSCC(V: number, adj: Record<number, number[]>): number {
  const visited: boolean[] = new Array(V).fill(false);
  const stack: number[] = [];

  function dfs(v: number): void {
    visited[v] = true;
    for (const nei of adj[v] || []) {
      if (!visited[nei]) dfs(nei);
    }
    stack.push(v);
  }

  for (let i = 0; i < V; i++) {
    if (!visited[i]) dfs(i);
  }

  const transpose: number[][] = Array.from({ length: V }, () => []);
  for (let u = 0; u < V; u++) {
    for (const v of adj[u] || []) {
      transpose[v].push(u);
    }
  }

  visited.fill(false);
  let count = 0;

  function reverseDFS(v: number): void {
    visited[v] = true;
    for (const nei of transpose[v]) {
      if (!visited[nei]) reverseDFS(nei);
    }
  }

  while (stack.length > 0) {
    const node = stack.pop()!;
    if (!visited[node]) {
      reverseDFS(node);
      count++;
    }
  }

  return count;
}

const graph: Record<number, number[]> = {
  0: [1],
  1: [2],
  2: [0],
  3: [4]
};

console.log("Number of Strongly Connected Components:", kosarajuSCC(5, graph));