A country has n cities and m bidirectional roads (some may be destroyed). Building a library costs c_lib and repairing a road costs c_road. Every city must have access to a library, either directly or through repaired roads. Find the minimum cost. Google asks connected-component problems to test graph fundamentals and cost optimization.
For cities, roads (forming a triangle), c_lib = 2, c_road = 1: build library and repair roads for a cost of . If c_lib = 1 instead, just build libraries for (cheaper than roads).
This boils down to a graph connectivity question. How do connected components help you decide?