Given a directed graph $G=(V, E)$, and two vertices u and v in V, we call vertex v is reachable from u, if there exists a directed path from u to v. A vertex s in V is called a source vertex if every vertex in V is reachable from s.

(a) (8%) Given a directed graph $G=(V, E)$, and a specified vertex v in V, design a linear time algorithm (i.e. your algorithm should run in $O(|V|+|E|)$ time) to determine if v is a source vertex. You need to describe the data structure used in your algorithm.

(b) (8%) Given a directed acyclic graph (DAG; a directed graph is acyclic if it contains no directed cycles) $G=(V, E)$, you are asked to determine if G contains a source vertex. If you apply the algorithm of subproblem (a) on every vertex of G, you will get an algorithm runs in $O(|V|^2+|V||E|)$ time. It is not desirable. Design a more efficient algorithm for this problem. Analyze the time complexity of your algorithm.

(c) (9%) Given a directed graph $G=(V, E)$, you are asked to determine if G contains a source vertex. Note that the given graph may contain directed cycles. As in subproblem (b) an $O(|V|^2+|V||E|)$ time algorithm is not acceptable. Design a more efficient algorithm for this problem and analyze the time complexity of your algorithm.