1. Given a directed graph G of n vertices and m edges, let s be a vertex of G. (a) Design an O(m + n) time algorithm to determine whether the following is true: there exists a path from s to v in G for every vertex v of G. (10 points) (b) Design an O(m + n) time algorithm to determine whether the following is true: there exists a path from v to s in G for every vertex v of G. (10 points) Note: The input is the adjacency lists for G. This means that all information needed in your algorithm must be computed from the adjacency lists. Note: Here is an application of your algorithms for (a) and (b). We say that a directed graph G is strongly connected if for every pair of vertices u and v, there exists a path from u to v and there also exists a path from v to u in G. An interesting observation is that G is strongly connected if and only if there exists a path in G from s to v and there is also a path from v to s for every vertex v of G (you may think about how to prove this observation). In light of the observation, we can determine whether G is strongly connected in O(m+n) time by using your algorithms for the above two questions (a) and (b).
