Graph Theory37 sections · 1633 units
Open in Course

Problem - Road Reparation

CSES - MST basic

You have n cities and m possible roads. Each road has a repair cost. You want to repair some roads so all cities are connected. Find the minimum total cost to connect all cities. If it is impossible, output "IMPOSSIBLE".

This is an MST problem. You need to select n1n-1 roads that connect all cities with minimum total cost. If the graph has fewer than n1n-1 edges or the graph is disconnected, output IMPOSSIBLE. Use Kruskal's algorithm: sort edges by cost, add them greedily, skip edges that create cycles.