Analysis

Observations: If u is gray when v is blackened, then v is forward reachable from u. If u precedes v in L, then u was either white or gray when v was blackened. If white, then v is not forward reachable from u.

Let u be the first node in L (after the first call to topological sort).

• It is only forward reachable by nodes in its same strongly connected component. Why? Picture.
• So, any node v that is backward reachable fom u shares u's strongly connected component.
• Also, any v in u's strongly connected component is backward reachable from u (of course).
• Visit(v, G_t, l) returns all (and only) nodes backward reachable from u.
• So, we correctly identify (and blacken) component 1.
• Remove all the component 1 nodes from L and G^T.
• Repeat!