GSJANC - Editorial

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]: Contest Page | CodeChef
[2]: IO6t9o - Online C++0x Compiler & Debugging Tool - Ideone.com