Hackerrank Kingdom Connectivity

I am trying to solve this problem, [https://www.hackerrank.com/challenges/kingdom-connectivity][1] .
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 ?
[1]: https://www.hackerrank.com/challenges/kingdom-connectivity

i can help you a bit about this for an directed graph cycle exists in the graph only when there is a backedge you can check for the back edge for a graph as keep an array to trace the visited time of the node (it is simply counter ) and if any edge leads you to a node whose counter is less than this node it means that node is its ancestor and you have found a back edge which reveals the existence of a cycle in the given graph . I will try to solve it by myself then you the same here.:stuck_out_tongue:

Thanks for your reply. :slight_smile: But the problem here is, that I need to detect if there is a cycle between two nodes 1 and n and not just in the graph. For example cycle may exist, but it should also lie in some path joining 1 and n.

Keep a array(A) which tells whether last node is reachable by the current node or not.Just use the Strongly connected components(SCC) concept to find out if there is a cycle or not.After finding the SCC, just check for every node in the SCC,with the help of the array mentioned above, whether the last city is reachable by it or not. So, with the help of ‘A’ you can determine whether to include the cycle in the solution or not.