Assignment 3 due by the end of class Wednesday January 31 2001.

SCC stands for strongly connected component. A sink SCC is an SCC whose vertex set is a sink in the condensation dag of the digraph.

1. The following algorithm determines reachability in a digraph. Assume that the results of the algorithm are stored in an n-by-n boolean array R.
```for each vertex v
for each vertex w not equal to v
determine by traversal whether w is reachable from v
endfor
endfor
```
• Design in detail the most efficient algorithm you can which uses R to identify the SCCs of the digraph.
• Using Theta notation, give the worst case running time of your algorithm. (In your analysis, do *not* include the time of the code given above.)
2. Consider the recursive version of DFS (e.g. on page 9 of the web notes) performed on a digraph. The dfs number for each vertex is the order in which it is visited.
• Prove or disprove: for each SCC, the dfs numbers of these vertices forms a consecutive subsequence of {1,...,n}.
• Prove or disprove: for each sink SCC, the dfs numbers of these vertices form a consecutive subsequence of {1,...,n}.
• Give a counterexample, or give an *outline of a proof* (you do not have to provide all details): for any SCC, the vertices of this SCC form a subtree of the dfs forest of the digraph.