Problem Link:
Author: Parth Trehan
Editorialist: Parth Trehan
Difficulty:
Easy-Medium
Prerequisites:
Graph Theory, BFS
Problem:
We need to traverse a graph from node 1 to node N. Some nodes of the graph are dependent on other nodes i.e. we can cross/pass some nodes iff we have already visited the nodes provided in the information.
Explanation:
We maintain our graph in an adjacency list. We even maintain an array with the extra information. Now, we traverse this graph from node 1 using the BFS graph traversal technique. As usual we maintain a queue for the BFS traversal. In addition to the given contraint, we maintain another queue.
If we are able to pass a node i.e. no extra information is entered about it, we simply mark the node visited. If we come across a node whose entry is present in the extra information, if we have already visited the node associated to it, we simply treat it as a regular node and mark it as visited too but the node associated to it is node visited, we push it in our other queue and remove it’s entry from the queue we maintained for BFS traversal.
After we have visited all the possible visitable nodes, we check our newly manitained queue. If some nodes are now visitable, we push those nodes back in our BFS queue and start the traversal again. In the process, if we pass through the Nth node, we return back to the calling function.
Now, if at end, all the visitable nodes are visited and the nodes present in the new maintained queue cannot be visited according to the constraint, it will leave our BFS traversal queue empty and this could be the condition using which we would break out of the loop.