Strongly connected components

Definition

Graph with marked strongly connected components

Let [math]\displaystyle{ G=(V,A) }[/math] be a directed graph. Consider the following equivalence relation on the nodes: [math]\displaystyle{ v\in V }[/math] and [math]\displaystyle{ w\in V }[/math] are equivalent if, and only if, there is a path from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] and a path from [math]\displaystyle{ w }[/math] to [math]\displaystyle{ v }[/math] in [math]\displaystyle{ G }[/math]. The equivalence classes are called the strongly connected components (SCC) of [math]\displaystyle{ G }[/math].

Input

A directed graph [math]\displaystyle{ G=(V,A) }[/math].

Output

A set of sets of nodes. Each set of nodes contains exactly the nodes of one SCC. The correspndence between SCC and sets of nodes is one-to-one.

Pseudocode

STRONGLY-CONNECTED-COMPONENTS(D)

STRONGLY-CONNECTED-COMPONENTS(D)
1 call DFS(D) to compute finishing times f[v] for each vertex v ∈ V
2 compute DT (w.r.t. step 3)
3 call DFS(DT), but in the main loop of DFS, consider the vertices in order of decreasing f[v] as computed in step 1
4 output the vertices of each tree in the DFS forest of step 3 as a separate strongly connected component

Known algorithms

1. Kosaraju

Further information

STRONGLY-CONNECTED-COMPONENTS runs in linear time.