Cities

Bitland has n cities that initially have no connecting roads. Your task is to design a class that supports adding a road between two cities and querying if there is a route between two cities.

You may assume that the number of cities is at most 50 and that the methods of the class are called at most 100 times.

In a file cities.py, implement a class Cities with the following methods:

• constructor with the number of cities as a parameter
• add_road adds a road between two cities
• has_route checks if two cities are connected by a route

class Cities:
    def __init__(self,n):
        # TODO

    def add_road(self,a,b):
        # TODO

    def has_route(self,a,b):
        # TODO

if __name__ == "__main__":
    c = Cities(5)
    c.add_road(1,2)
    c.add_road(1,3)
    c.add_road(4,5)
    print(c.has_route(1,5)) # False
    c.add_road(3,4)
    print(c.has_route(1,5)) # True