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
    
  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.