= Strongly Connected Components =

'''Definition (StronglyConnectedComponents)''' A strongly connected component of a directed graph G=(V,E) is a maximal set of vertices C⊆V such that ∀u,v∈C, we have both u--->v and v--->u. (---> signifies a path)

'''Algorithm (FindingStronglyConnectedComponents)''' Strongly-Connected-Components(G)

   1. call DFS(G) to compute finishing times f[u] for each vertex u
   1. compute G^{T}
   1. call DFS(G^{T}), but in the main loop of DFS, consider the vertices in order of decreasing f[u] (as computed in line 1)
   1. output the vertices of each tree in the depth-first forest formed in line 3 as separte strongly connected components.

attachment:SCC.jpg