Graph Theory37 sections · 1633 units
Open in Course

Problem - Building Roads

CSES 1666 - MSF for components

You are given a graph with nn nodes. Some nodes are already connected. You need to add the minimum number of edges to make the graph connected. Output the number of edges to add and which edges to add. This is not a standard MST problem. It is a component connectivity problem.

But MST ideas help. What you do: count components, then connect them with exactly k1k-1 edges. No weights involved. Find all components first, then link one representative from each component to the next.