This is a variation of a question I came across in one of the mock-interview videos.
Assume there's a bunch of routes
ex: [rome->dallas, dallas->rome, london->paris, paris->frankfurt, london->dallas, frankfurt->rome] etc. Now I want to add a new location to this route ex: delhi. The question is to to find the minimum no. of connections i need to build such that I can cover all the above places from Delhi ?
My solution is:
- Build a graph and get the list of strongly connected components in that graph.
- Add an edge from this new location to at-least one node of every component in the list of SCC's. Since every node is connected to every other in a SCC, adding an edge to any one of the nodes should work.
Does this solution make sense ? I'm unable to come up with a way to prove that this can work in every situation. Is there any drawbacks of this solution. Please share your inputs/comments.