Algorithm Design

Problem 2. Let G(V,E) be a directed graph and let sV be a source node (you may assume that the graph is given in an adjacency list format). We say that a node is reachable from s if there is a directed path to it. (see illustration). Design an algorithm that finds and returns all nodes vV such that there exists, in G, both a path from s to v and a path from v to s. The input to you algorithm is G and s and the output the set of nodes. Prove the correctness of your algorithm and analyze its run time. For full credit, your algorithm should run in time O(n+m) where n=V and m=E. For 8/10 pts, your algorithm can run in O(n2+nm) time. Note that for BFS it doesn't matter whether the input is the adjacency list of a directed or undirected graph. (a) Some nodes are reachable (b) Some nodes are reachable (c) All nodes are reachable in in one direction. in both directions. both directions. Figure 1: Illustration of Problem 2