PROBLEM LINK:
Author: rahul_ojha_07
Tester: rahul_ojha_07
DIFFICULTY:
Easy
PREREQUISITES:
Graph Theory, BFS
PROBLEM:
Check if the given path is connected or not after removing a city from the path.
EXPLANATION:
This problem can be solved using a simple graph traversal algorithm such as Depth First Search.
It can be seen that the input is in the form of a graph and thus each city can be treated as the Node of a graph and the path between the cities can be treated as the edges of a graph. Now for the question,
First of all, apply Depth First Search on the given cities and traverse through all the cities and store the number of the city reached in a variable A
after that again apply Depth First Search on the cities after the removal of cities and store the number of cities reached on another variable B.
then compare the number of Nodes reached in both the cases if the difference between A and B is more than one then we can conclude that some cities cannot be reached after removal of the city Z.
if the difference is equal to 1 then it is concluded that the cities are still connected by the removal of city Z.
Author’s solution can be found here.