I am trying to solve this problem, [https://www.hackerrank.com/challenges/kingdom-connectivity] .
What I have done so far:
- We want to count the number of paths from 1 to n, in a directed cyclic graph, So, I plan to do a dfs with a visited array keeping the count of occurrences of the node till now.
- I googled about how to detect a cycle existing between a path from the 1 to n, I found that we color graphs white(if unvisited), gray(if visited, but one or more descendants are unvisited) and black(if visited, and all descendants are visited), so finding a cycle would be equivalent to visiting a gray colored node, during dfs (a back edge).
- However I am a bit confused as to how do I ensure that the cycle is existent between the path from 1 to n.
I am thinking of taking another array cycled which would keep the information about whether the node is reachable from a cycle or not.
However I am not quite getting as to how do I allow multiple visits with the above thing in mind, can someone give some leads, hints ?
I went through the solution given by lucas, http://lucasou.com/kingdom-connectivity/, and I feel that doing a dfs using a stack explicitly instead of using the system stack using recursion is not possible in this case, as there is no way to track the information as to when do we need to push out the nodes from the stack. Can someone tell me if I am thinking right ?