Wires to Add — Solution & Editorial

Back to the Problem

Adding one edge can merge at most two components, and connecting component representatives in a chain achieves it: answer = C − 1.

Complexity: O(N + M)