MCO16405 - Editorial

dynamic-programming
easy-medium
mco16405
scc

#1

PROBLEM LINK:

Practice
Contest

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* be the answer for the i-th node. Then, we can calculate this dp in reverse topological order. dp* = cnt* + max(dp[j]) for all outgoing edges i -> j, and cnt* 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: