IDorando's blog

By IDorando, history, 7 weeks 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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you know dp?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Of course.

    • »
      »
      »
      7 weeks 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

      • »
        »
        »
        »
        7 weeks 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.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why do it with BFS? DFS is easier

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Sort graph topologically and then do dp, in which dp[i] is the number of ways to reach vertex i from starting vertex, you can view my submission to similar problem (shortest path instead of number of ways) here.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, I didn't think about using the topological sorting. Everything makes so much sense now. Thank you, it really helped me out!