Hello, Can anyone please tell how to solve below problem — There exists a special graph which has directed M edges and N nodes and graph contains no cycles. Count the number of ways to reach different nodes from S. A way is called different from others if the destination node or used edges differ. As the ways can be large, print the ways modulo 1000000007. Include source node as destination also. 1 <= S, N <= 100005 (S=source vertex) (N=number of nodes) 1 <= M <= 200005 (number of edges) 1 <= x , y <= N (edge from x to y)
My approach is to use dp on tree 1)Make a reverse graph (all edges are in reverse order) 2)call DP recursive function for all nodes who are not yet visited 3)Inside Dp recursive function call for number of ways to reach to parent of current node from Source(S)(Using the reverse graph) and add all those ways to dp[current_node] 4)return dp[current node] But this approach is giving TLE in some testcases. Please suggest some ideas... Problem link
Thanks :)
Do topology sort. let dp[i] be the number of ways to reach different nodes from i-th node in topology sort. dp[i]=dp[a[1]]+dp[a[2]]+...+dp[a[k]] where a[1],a[2]...a[k] are nodes in which is directed edge that goes from i-th node in topology sort. lets k be z-th node in topology sort, answer will be dp[z].
Thanks, It Worked got AC. can you please also tell whats wrong in my approach