SCC
Document last modified: 
Strongly-Connected-Components (G)
1    Call DFS (G) to compute finishing times f[u] for each vertex u
2 Compute GT
3 Call DFS (GT), but in the main loop of DFS, consider the vertices in order of decreasing f[u] (as computed in line 1)
4 Output the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component. 
Do this by starting with the smallest f[u] value (from GT) and use the predecessor array π, from GT
Components that are connected in G are still connected; e.g. (abe, cd) since G contains (b, c).

DFS(G) is given below.

    

  1. Complete the table for G.
  2. Give f[u] in decreasing order.
  3. Draw GT.
  4. Find DFS(GT), but in the main loop of DFS at Line 5, consider the vertices in order of decreasing f[u]. Assume that the adjacency list is ordered alphabetically at Line 4 of DFS-Visit.
  5. On the graph above, circle GSCC
G   a   b   c   d   e   f   g   h
d                
f                
π                
GT   a   b   c   d   e   f   g   h
d                
f                
π                
DFS (G)
       -- Initialize arrays
1 for each vertex u ∈ G.V do
2    u.color ← WHITE
3    u.π ← NIL
4 time ← 0
5 for each vertex u ∈ G.V do
6     if u.color = WHITE then
7        DFS-Visit (G, u)
DFS-Visit (G, u)
1       u.color ← GRAY
2 time ← time + 1
3 u.d ← time
4 for each vertex v ∈ G.Adj[u] do
5    if v.color = WHITE then
6       v.π ← u
7       DFS-Visit (G, v)
8 u.color ← BLACK
9 u.f ← time ← time + 1