I was trying a problem kingdom connectivity in which we had to count the no. of different ways to reach from a given source node to a given destination.There can also be infinite paths in that case we need to output "INFINITE PATHS". Suppose steps[i] array keeps track of the no. of ways to reach ith node.we can simply apply DP to solve this.starting from the 1st vertex loop through all vertices.For vertex i, for all neighbours of i steps[neighbour]=steps[neighbour]+(no. of edges b/w neighbour & i)*steps[i].this can also be replaced by steps[neighbour]=steps[neighbour]+steps[i] if no. of times the neighbour appears in the adjacency list=no of edges b/w the vertex i & that neighbour.We compute this for all vertices and then check steps[destination]. However this is possible only if the graph doesn't have a loop in it. If a loop exists then there would be infinite loop in the code. So to check if a loop exists I used modified Kosaraju's Algorithm in which I used a Break in the dfs_loop2 if an SCC has more than 2 nodes that would imply the existance of a loop. I am getting wrong answer. I think it might be heap space overflow in the adjacency list.if anyone has any other approach kindly let me know. You can find my code at:http://ideone.com/ieBYb#li_6wlDA link to the problem: https://www.interviewstreet.com/challenges/dashboard/#problem/4f40dfda620c4
kindly help. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
