es represent the road between two cities. The Department of Highways (DOH) decides to install the cameras to detect the bad driver. To reduce the cost, the cameras are strategically installed in the cities that a driver must pass through in order to go from one city to another city. For example, if there are two cities A and B such that the path that goes from A to B and the path that goes from B to A must pass the city C, then C must install the camera. Sup
Suppose that the road network is defined by the undirected graph, where the vertices represent cities and edges represent the road between two cities. The Department of Highways (DOH) decides to install the cameras to detect the bad driver. To reduce the cost, the cameras are strategically installed in the cities that a driver must pass through in order to go from one city to another city. For example, if there are two cities A and B such that the path that goes from A to B and the path that goes from B to A must pass the city C, then C must install the camera. Suppose that there are m cities and n roads. Write an O (m + n) to list all cities where cameras should be installed.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 3 images