Given a directed graph G = (V,E), suppose we have a function t : V R⁺ which maps each vertex v V to a non-negative value t(v). We say that a vertex v can achieve a score s if there exists some node w V such that v can reach w and t(w) = s. We denote the maximum score that a vertex v can achieve by

S(v) = max t(w).

{w : v can reach w}

Note that in the problems below, you may not assume any relationship between |E| and |V | beyond the general). Additionally, you may assume for each part that you have either an adjacency matrix or an adjacency list structure for your graph G, but not both!

2. Design an algorithm which reports the value S(v) for every vertex v V with total time complexity O(|V |+|E|) in the case that G is a DAG (Directed Acyclic Graph). Briefly justify correctness and time complexity.

Start at the vertex without any incoming edges.

Hint: Consider the SCCs in the graph G.