Strongly Connected Components

largest subset of vertices C⊂V such that for every pair of vertices v,w ∈C we have a path from v to w and a path from w to v

algorithm

• Call dfs for the graph GG to compute the finish times for each vertex.
• Compute GT.
• Call dfs for the graph GTGT but in the main loop of DFS explore each vertex in decreasing order of finish time.
• Each tree in the forest computed in step 3 is a strongly connected component. Output the vertex ids for each vertex in each tree in the forest to identify the component.