**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.**