PROBLEM LINK:Author: Zi Song Yeoh DIFFICULTY:EASYMEDIUM PREREQUISITES:STRONGLY CONNECTED COMPONENTS, TOPOLOGICAL SORT, DP ON DAG PROBLEM:Given a directed graph, find the sum of values of nodes you can visit from each node. EXPLANATION:The first subtask implies that the graph is undirected. Thus, the problem can be solved with either dfs/bfs or dsu. We just have to find the connected components and we can easily find the answer for each node in $O(n)$. For the second subtask, we have a DAG (Directed Acyclic Graph). Let $dp[i]$ be the answer for the $i$th node. Then, we can calculate this dp in reverse topological order. $dp[i] = cnt[i] + max(dp[j])$ for all outgoing edges i > j, and cnt[i] is the number of people on $i$th node. This subtask can also be solved in $O(n)$ time. To solve the whole problem, we have to deal with cycles here. However, this is not a problem. We just have to compress the Strongly Connected Components of the graph into a single vertex and apply the same solution for DAG. You can refer to the codes for details or google how to compress SCC of a graph. Time complexity is still $O(n)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. RELATED PROBLEMS:asked 20 Feb '17, 13:34
