Consider a directed graph that has a weight w(v) on each vertex v. Define the reachability weight of vertex v as follows:

r(v)=max{w(u)|u is reachable from v}

That is, the reachability weight of v is the largest weight that can be reached from v. Answer the following questions:

a. Assume the graph is a DAG. Describe a linear time algorithm to compute the reachability weight for all vertices.

b. Assume that the graph is a general directed graph (with possible cycles). Describe a linear time algorithm to find the reachability weight for all vertices.