I think I understand now why we can't guarantee that the lowest post number in the original graph is a sink (it may have outgoing edges to vertices that have already been visited before it).
But why is the case different for reversing the graph and looking at the highest post number? Why is this a foolproof way to find a vertex in the sink SCC of the original graph?
On
The important thing is that, for two strongly connected components A and B connected by an edge (A, B), that is, the edge is incident from A to B, the highest post number of A is always going to be greater than the highest post number of B.
Let's denote the highest post number of a strongly connected component C as h(C) from now on.
But why is the case different for reversing the graph and looking at the highest post number? Why is this a foolproof way to find a vertex in the sink SCC of the original graph?
As you say, first, you look at the maximum h(C). All edges incident on C must be outgoing or h(C) wouldn't be largest, according to the first paragraph.
If you reverse the graph now, all edges incident on C must be incoming; they have simply been reversed. Running a depth-first search (DFS) on C, will yield a tree with only the vertices of C now because it has been "isolated" and is a sink. SCCs retain the property that every vertex u is reachable from every vertex v within that SCC after reversal, so the SCC's vertices are not affected.
Now that the first SCC has been established, DFS goes on to D, which has the second-highest h(D). As per the first paragraph, for any SCC denoted E, h(D) is greater than h(E). Only h(C) is greater than h(D), but all vertices of C have already been visited! Therefore, D is isolated, just like C: all edges connecting D to any SCC E are incident to D, except for C, so D is not a sink. C has been visited already, though, so the DFS won't visit it again. The entirety of D will thus be understood as another separate, strongly connected component.
This process goes on until the very last SCC and yields a forest, in which every tree corresponds to one strongly connected component.
I think we reverse the graph for the following reason: this is a stack operation.when we reverse the graph,we get the sink SCC for the reversed graph firstly and we push it to the top of the stack...we repeat the operation and finally the graph is null.then we pull the point set from the bottom of the stack,which is the sink SCC for the original graph.