Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя YGBoss007

Автор YGBoss007, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.