PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY-MEDIUM
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.