IDorando's blog

Number of paths between 2 vertices in a directed graph
By IDorando, history, 2 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Do you know dp?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Of course.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why do it with BFS? DFS is easier

          → Reply