Problem 1, (11 marks) A digraph G = (V. E) is called a one-way connected graph if for every two vertices u, v E 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 sufficient condition for a digraph to be one-way connected. Prove its correctness (i.e., prove it is a necessary condition and also a sufficient 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 sufficient 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 efficient 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.)