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

Number of paths between 2 vertices in a directed graph
Автор IDorando, история, 2 года назад, По-английски

Hi Codeforces! There is a problem where it asks you to find the the number of paths between 2 vertices in a directed graph. There are no cycles and you are not allowed to visit the same node multiple times. I have seen some solutions in O(n!) and O(n ^ 2) but I need something more efficient since the number of nodes N is 100000 and the number of edges is 300000. I would really appreciate if you could give me some ideas!

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

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

Do you know dp?

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Of course.

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      You can do it using dp. The base case would be the node you are trying to reach. Try solving this problem. It's the same idea except on a grid

      → Ответить
      • »
        »
        »
        »
        2 года назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        It is not that easy. Think about this directed graph : 3 1, 3 2, 1 4, 2 1, 2 4, (sry idk how to post an image)

        The source node is 3 and you want to find out the number of ways to get to node 4. If you make something like a BFS there is a possibility to lose some cases. From node 3 it will add one way to nodes 1 and 2 having dp[1] = 1 and dp[2] = 1. But if your next node in the queue is 1 it will add to dp[4] 1 way which is wrong because it misses the 3 -> 2 -> 1 -> 4 case.

        → Ответить