You are not logged in. Please login at www.codechef.com to post your questions!

×

# 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:

asked 20 Feb '17, 13:34

6★zscoder
62812
accept rate: 6%

19.0k348495533

 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

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,788
×1,409
×26
×4

question asked: 20 Feb '17, 13:34

question was seen: 491 times

last updated: 21 Feb '17, 19:06