YGBoss007's blog

Help needed in Coin Collector-CSES Problem Set
By YGBoss007, history, 4 years ago, In English

Your text to link here... My logic is as follows: First of all, we can get all the SCC's of the graph with their respective sums. Now we can make a condensed graph sort of thing, where each SCC acts as a node. I'm not able to get what to do after that? I gave a hard thought of maintaining DP after that but couldn't get on with the recurrence relations. Any help would be appreciated.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As you might have guessed that if we add SCC to our final result, the whole value of that SCC will get added. Further, what we can now do is for each SCC, we find out how many other SCC's it can visit. Here we will call a DFS so that only once we add a particular node value to its corresponding DP. That would mean dp[i] = sum of dp[adjacent nodes from i] + current node value DFS will take care that you don't add a value multiple times.

→ Reply