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

×

MCO16405 - Editorial

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[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, 13:34

zscoder's gravatar image

6★zscoder
62811
accept rate: 6%

edited 21 Feb, 19:06

admin's gravatar image

0★admin ♦♦
15.9k347484508

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,259
×1,071
×12
×4

question asked: 20 Feb, 13:34

question was seen: 253 times

last updated: 21 Feb, 19:06