PROBLEM LINK : Problem 2
Editorialist : Subhesh
DIFFICULTY : EASY
PREREQUISITES : Graph Theory
Problem :
Given Route of Buses, You have to find a bus stop from where the maximum number of stops supervisor has to travel to reach any other bus stop is minimized.
Quick Explanation :
Create Graph of the given routes (undirected Graph as buses run in both directions). Now you just have to find out a node from which every other node is at minimum possible distance.
Explanation :
We shall create graph in which node corresponds to a bus stop and edges will specify the path which supervisor can travel.
consider Given Example:
The corresponding graph would be:
Now we have to minimize the maximum number of stops to travel to reach any other bus stop i.e. Best of the worst.
Let’s just assume each node as office of supervisor one by one and find out the best one:
Node 1 : max distance node is 6 which at 4 distance
Node 2 : max distance node is 6 which is at 3 distance
Node 3 : max distance node is 6 which is at 4 distance
Node 4 : max distance node is 1 or 3 or 6, all at 2 distance
Node 5 : max distance node is 1 or 3 which is at 3 distance
Node 6 : max distance node is 1 or 3 or 7 which is at 3 distance
Node 7 : max distance node is 1 or 3 or 6, all at 3 distance
So Node 4 (Bus stop 4) is the best stop no. to locate office of the supervisor as max distance possible to any other bus stop is 2 which is minimum among all other bus stop.
a)
The corresponding graph would be :
Now you can compare and figure out that the Node 6 (Bus stop 6) is the best possible stop no as maximum distance to any node is 4.
b)
Corresponding graph:
Again you can compare and figure out that the Node 15 (Bus stop 15) is the best possible stop as maximum distance to any node is 5
c)
Corresponding Graph:
Again you can compare and figure out that the Node 6 (Bus stop 6) is the best possible stop as maximum distance to any node is 5.