So I found this handout which proposes & proves the following algorithm for finding SCCs of a directed graph:
- Run DFS on the reversed directed graph and keep track of the post numbers for each node.
- In order of highest post number to the lowest post number, run a normal connected components algorithm.
- Profit
This is based on the lemma that if C and C' are two SCCs and C goes to C', then the highest post number in C is greater than the highest post number in C'.
So why can’t we just run DFS on the normal directed graph and go from lowest post number to highest post number? This reversed graph thing seems a bit unnecessary, to be honest.