### IDorando's blog

By IDorando, history, 7 weeks ago, 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!  Comments (7)
 » Do you know dp?
•  » » Of course.
•  » » » 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 →   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 and dp = 1. But if your next node in the queue is 1 it will add to dp 1 way which is wrong because it misses the 3 -> 2 -> 1 -> 4 case.
•  » » » » » Why do it with BFS? DFS is easier
 » 7 weeks ago, # | ← Rev. 2 →   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.
•  » » Oh, I didn't think about using the topological sorting. Everything makes so much sense now. Thank you, it really helped me out!