Editorialist: Kabeer Seth
Connected Components, BFS, Diameter of Tree
Optimally place source points of information in each of the connected components to obtain minimum time.
Find all the connected components and then in each connected component place your source node as the center of the diameter, the time taken to spread will be diameter/2 for each connected component, now just compute the maximum of all the diameter/2.
The center of the diameter will be the most optimal point as the longest possible path in any connected component will be the diameter, if we choose any other points it will take more than diameter/2 time.
Author’s solution can be found here .