Strongly connected components

A stongly connect component of a graph G = (V,E) is a maximal set of vertices U sub-set-of V such that for every pair of vertices u and u in V, we have both u --> v and v --> u; (--> is reachable ) that is vertices u and v are reachable from each other.

Transpose graph : G' = (V,E') where E' = {(u,v : (v,u) in E}. E' consists of the edges of G with their direction reversed. Given an adjacency list representation of G, the time to create G' to O(V+E). G and G' have exactly the same strongly connected components : u and v are reachable from each other in G if and only if they are reachable from each other in G'.

Strongly-connected-components(G)
1 call DFS(G) to compute finishing times f[u] for each vertex u
2 compute G'
3 call DFS(G'), but in the main loop of DFS, consider the vertices in order of decreasing f[u]
4 output the vertices of each tree in the depth-first forest of step 3 as a separate strongly connect component.