Near the end of class, we discussed the book's TransitiveClosure algorithm (from end of Section 4.2). It does a DFS from every vertex v, and then stores the "marked" array from each. Then in constant time, we can answer, for a given v and w, whether there is a path from v to w. Single DFS: Time O(V+E) Space O(V) Transitive Closure (one DFS per vertex): Time O(V*(V+E)) Space O(V*V) Next we observed that we might use SCC's to speed this up. Suppose digraph G has only S strongly-connected components. S may be quite a bit smaller than V, the number of vertices. Idea: if u and v are in the same SCC, then the set of reachable vertices for u is exactly the same as the set for v. So, we could speed up TransitiveClosure as follows: * compute the SCC's, in O(V+E) time * do a DFS from only one vertex u per SCC * reuse u's "marked" array for every other vertex in its component In this way, we get: Time O(S*(V+E)) Space O(S*V) If S is small, that is a big improvement. But this is not in the book. (With more work, we might improve the space further to O(S*S+V), do you see how?)