×

MCO16405 - Editorial

Author: Zi Song Yeoh

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.

RELATED PROBLEMS:

6★zscoder
62811
accept rate: 6%

18.4k347492528

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,511
×1,284
×26
×4

question asked: 20 Feb '17, 13:34

question was seen: 368 times

last updated: 21 Feb '17, 19:06