PROBLEM LINK: [Contest][1]
DIFFICULTY: Medium
PREREQUISITES: Graphs
PROBLEM:
The aim is to find the number of cities from source to destination.
If the source and destination are different a BFS traversal with each layer adding city to path, will be counted.
If source and destination are same, still a BFS has to be applied to find a cycle path.
Also, there is a possibility that the path does not exists.
SETTER’S SOLUTION: [Solution Link][2]
APPROACH:
We need an array dist to store the distances from S to E.
For BFS, we need queue q to store traversal nodes (cities), global array visited to store which nodes (cities) have been visited already.
A simple BFS from node (city) S has to be run. Complexity of this solution is O(N+M).
From S we add each layer by layer increment each child node’s distance from S to be its distance from parent node+1. Here each node specifies each city and after traversal, we can check the visited array has city E i.e. index E visited or not. If it is visited, we print dist[E] along with YES else we print NO.
[1]: CodeChef: Practical coding for everyone
[2]: IO6t9o - Online C++0x Compiler & Debugging Tool - Ideone.com