Can somebody please tell how to solve this problem using SQRT decomposition method. I did'nt found any correct way to implement?
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