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!
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
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.
Why do it with BFS? DFS is easier