Why does SCC Work? (cont.)

II-Why does SCC Work? (cont.)-II

●The next root chosen in the second DFS is in SCC C2 such that f(C) is maximum over all SCC’s other than C1

●DFS visits all vertices in C2

■the only edges out of C2 go to C1, which we’ve already visited

Þ The only tree edges will be to vertices in C2

●Each time we choose a new root it can reach only:

■vertices in its own component

■vertices in components already visited

1.