Strongly Connected Components (SCC)

A strongly connected component (SCC) is a maximal group of vertices in a directed graph such that every vertex is reachable from every other vertex in the group.

Strongly connected components reveal tightly coupled subgraphs and are fundamental in graph analysis and dependency management.

What Is a Strongly Connected Component?

In a directed graph, a set of vertices forms an SCC if:

• For every pair of vertices u and v:

  • There is a path from u → v
  • There is a path from v → u

Example:

A → B → C
↑         ↓
└─────────┘

Vertices {A, B, C} form a single SCC.

SCC vs Connected Components

Why SCCs Matter

Strongly connected components are used in:

• Dependency analysis
• Program flow analysis
• Deadlock detection
• Optimizing graph algorithms
• Condensing graphs into DAGs

Popular Algorithms for SCC

Two classic linear-time algorithms are commonly used:

1. Kosaraju’s Algorithm
2. Tarjan’s Algorithm

This section focuses on Kosaraju’s algorithm because it is easier to understand conceptually.

Kosaraju’s Algorithm

Kosaraju’s algorithm finds SCCs in three steps:

1. Perform DFS and record vertices by finish time
2. Reverse all edges in the graph
3. Perform DFS in reverse finish-time order

Each DFS in step 3 identifies one SCC.

Algorithm Steps

Step 1: DFS and Stack Ordering

• Run DFS on the original graph
• Push vertices onto a stack after exploring all neighbors

Step 2: Reverse the Graph

• Reverse the direction of every edge

Step 3: DFS on Reversed Graph

• Pop vertices from the stack
• Run DFS on the reversed graph
• Each DFS traversal yields one SCC

Rust Implementation (Kosaraju)

use std::collections::{HashMap, HashSet};

type Graph = HashMap<i32, Vec<i32>>;

pub fn strongly_connected_components(graph: &Graph) -> Vec<Vec<i32>> {
    let mut visited = HashSet::new();
    let mut stack = Vec::new();

    // Step 1: Fill stack by finish time
    for &node in graph.keys() {
        if !visited.contains(&node) {
            fill_order(graph, node, &mut visited, &mut stack);
        }
    }

    // Step 2: Reverse the graph
    let reversed = reverse_graph(graph);

    // Step 3: Process vertices in reverse finish order
    visited.clear();
    let mut sccs = Vec::new();

    while let Some(node) = stack.pop() {
        if !visited.contains(&node) {
            let mut component = Vec::new();
            dfs_reversed(&reversed, node, &mut visited, &mut component);
            sccs.push(component);
        }
    }

    sccs
}

fn fill_order(
    graph: &Graph,
    node: i32,
    visited: &mut HashSet<i32>,
    stack: &mut Vec<i32>,
) {
    visited.insert(node);

    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if !visited.contains(&neighbor) {
                fill_order(graph, neighbor, visited, stack);
            }
        }
    }

    stack.push(node);
}

fn dfs_reversed(
    graph: &Graph,
    node: i32,
    visited: &mut HashSet<i32>,
    component: &mut Vec<i32>,
) {
    visited.insert(node);
    component.push(node);

    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if !visited.contains(&neighbor) {
                dfs_reversed(graph, neighbor, visited, component);
            }
        }
    }
}

fn reverse_graph(graph: &Graph) -> Graph {
    let mut reversed = HashMap::new();

    for (&node, neighbors) in graph {
        reversed.entry(node).or_insert_with(Vec::new);
        for &neighbor in neighbors {
            reversed.entry(neighbor).or_insert_with(Vec::new).push(node);
        }
    }

    reversed
}

Example Usage

fn main() {
    let mut graph: Graph = HashMap::new();

    graph.insert(1, vec![2]);
    graph.insert(2, vec![3]);
    graph.insert(3, vec![1, 4]);
    graph.insert(4, vec![5]);
    graph.insert(5, vec![4]);

    let sccs = strongly_connected_components(&graph);

    for (i, scc) in sccs.iter().enumerate() {
        println!("SCC {}: {:?}", i + 1, scc);
    }
}

Output (order may vary):

SCC 1: [1, 2, 3]
SCC 2: [4, 5]

Time and Space Complexity

Time Complexity

Space Complexity

Key Insight

Once SCCs are identified, the graph can be condensed into a DAG where each SCC becomes a single node. This greatly simplifies further analysis.

Summary

• SCCs apply to directed graphs
• Each SCC is maximally reachable in both directions
• Kosaraju’s algorithm finds SCCs in linear time
• SCC condensation produces a DAG

Playground Links

Rust - Kosaraju’s Algorithm