Strongly connected components (SCC)

In a directed graph, two vertices are in the same strongly connected component if each is reachable from the other via directed paths. SCCs partition the graph into maximal “mutual-reachability” groups. Compress each SCC into one node and you get a DAG (the condensation graph), which is a key reason SCC decomposition is so useful before other graph algorithms.

1) Definition

A subset C ⊆ V is strongly connected if for every u, v ∈ C, there is a directed path u ⇢ v and v ⇢ u. SCCs are maximal such subsets and are unique for a fixed graph.

2) Why SCCs matter

• Program/module analysis: mutual dependencies form SCC clusters.
• Graph simplification: collapse SCCs to a DAG and solve ordering on that DAG.
• Reachability structure: quickly reason about strongly coupled regions.

3) Example directed graph

Edges:
0->1, 1->2, 2->0, 2->3, 3->4, 4->5, 5->3, 4->6, 6->7, 7->6

SCCs:
SCC A = {0,1,2}
SCC B = {3,4,5}
SCC C = {6,7}

Condensation edges: A -> B -> C   (a DAG)

4) Kosaraju algorithm

1. Run DFS on original graph, pushing vertices by finishing time (stack/order array).
2. Reverse all edges (transpose graph).
3. Pop vertices in decreasing finish time; each DFS in transpose yields one SCC.

5) C — Kosaraju (adjacency matrix)

#include <stdio.h>
#include <string.h>

#define V 8

static int g[V][V], gt[V][V];
static int vis[V], order[V], ord_sz;

static void add_edge(int u, int v) { g[u][v] = 1; }

/* pass 1: DFS on original graph, store finish order */
static void dfs1(int u) {
    vis[u] = 1;
    for (int v = 0; v < V; v++)
        if (g[u][v] && !vis[v]) dfs1(v);
    order[ord_sz++] = u;   /* push by finish time */
}

/* pass 2: DFS on transpose graph to collect one SCC */
static void dfs2(int u) {
    vis[u] = 1;
    printf("%d ", u);
    for (int v = 0; v < V; v++)
        if (gt[u][v] && !vis[v]) dfs2(v);
}

int main(void) {
    add_edge(0,1); add_edge(1,2); add_edge(2,0);
    add_edge(2,3); add_edge(3,4); add_edge(4,5);
    add_edge(5,3); add_edge(4,6); add_edge(6,7); add_edge(7,6);

    memset(vis, 0, sizeof vis);
    ord_sz = 0;
    for (int i = 0; i < V; i++)
        if (!vis[i]) dfs1(i);

    /* build transpose: reverse each arc */
    for (int u = 0; u < V; u++)
        for (int v = 0; v < V; v++)
            gt[v][u] = g[u][v];

    memset(vis, 0, sizeof vis);
    printf("SCCs:\n");
    for (int i = ord_sz - 1; i >= 0; i--) {
        int u = order[i];
        if (vis[u]) continue;
        dfs2(u);
        printf("\n");
    }
    return 0;
}

6) Complexity

• Kosaraju: O(V + E) time with adjacency lists (two DFS passes + transpose build).
• Space: O(V + E) for graph + transpose + DFS state.
• With matrix representation, scans are O(V²) for teaching simplicity.

7) Trace summary