Graph Theory37 sections · 1633 units
Open in Course

Core Idea - Connect Component Representatives

(Chain them together)

Pick one node from each component as a representative. For example, use the smallest-numbered node in each component. Connect the representatives in a chain: (rep1,rep2)(rep_1, rep_2), (rep2,rep3)(rep_2, rep_3),., (repk1,repk)(rep_{k-1}, rep_k). This uses exactly k1k-1 edges. Any chain works.

The problem does not ask for minimum weight, minimum number of edges. A linear chain is the simplest solution that always works. You can find components with DFS, BFS, or DSU before connecting them.