An SCC is the maximum set of vertices such that every vertex can reach every vertex. A graph and it's reverse have the same SCCs.

Algorithm

$O(V+E)$

1. Generate the reverse graph ($G^r$)
   • Reverse all the edges (u->v turn into v->u)
2. Execute DFS of $G^r$ and save the post-order traversal
   • Every time a vertex reaches the end of its recursive call, add it to the list
3. Execute DFS of $G$ and visit the nodes in reversed-post-order traversal (the reverse of the previous result).
4. Each resulting tree is a new SCC.

Code

The code is way to messy to put here