Problem:
(A) Let G = (V, E) be a directed graph. Suppose a DFS of G is performed and the pre/post numbers of all vertices recorded. For two vertices u, v E V it is found that pre(o) = pre(u) +1.
Is (u,w) an edge in the graph and if so, what kind of edge is it? You must justify your answer - the justification is what counts here.
(B) Suppose you are given a directed graph G = (V, E). You want to find if there is a vertex u E V such that for any vertex vE V there is a path from v to u, i.e., w can reach to u. Suggest an algorithm to solve this problem. What is its running time?