You are given a digraph G = (V, E) in which each node u V has an associated weight wu (a positive integer). Define the array cost as follows: for each u V , cost[u] = weight of the cheapest node reachable, including u itself. Refer to Figure 1 for an example. Your goal is to design an algorithm that fills in the entire cost array.

Figure 1: In this graph (with weights shown for each vertex), the cost values of the nodes A, B, C, D, E are 2, 1, 5, 7, 3, respectively.

(a) Design a linear-time algorithm that works for DAGs. Write pseudocode, briefly explain how your algorithm works, and argue why the time complexity is linear. (Hint: You can process the vertices in the reversed topological sorting order, i.e., the increasing order of their post values. Assume that you can use this order directly in your pseudocode.) b) (b) Extend the algorithm you design in a) to a linear-time algorithm that works for all digraphs. Do not write pseudocode, instead, describe your algorithm in clear sentences. (Hint: Leverage the two-tiered structure of digraphs via the construction of strongly connected components, i.e., SCCs.)

5- C 1 5- C 1