Author: Zi Song Yeoh
STRONGLY CONNECTED COMPONENTS, TOPOLOGICAL SORT, DP ON DAG
Given a directed graph, find the sum of values of nodes you can visit from each node.
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.