Problem 1. A digraph G = (V,E) is called a one-way connected graph if for every two vertices u, v V , either there is a path from u to v or there is a path from v to u (but never both, so u and v can never be strongly connected).

a. (6 marks) State a necessary and sucient condition for a digraph to be one-way connected. Prove its correctness (i.e., prove it is a necessary condition and also a sucient condition). Note: Here is an incorrect answer. Consider the condition \every pair of vertices u and v are not strongly connected". It is obviously a necessary condition, since a one-way connected graph cannot have both a path from u to v and a path from v to u. While it is NOT a sucient condition, since a digraph satisfying this condition may not be a one-way connected graph (e.g.: In a digraph with three vertices 1, 2, 3 and two edges (1,2) and (3,2) each pair of vertices are not strongly connected, and the digraph is also not one-way connected since there is no path between 1 and 3).

b. (5 marks) Describe an ecient algorithm to determine whether or not an input digraph G = (V,E) is one-way connected. Analyze the running time of your algorithm. (Hint: Make use of the condition you state in part a.)