Connecting a Graph

Let $K$ be the number of connected components of the graph.

Adding one edge between two different connected components merges those two components, so one added edge can decrease the number of components by at most $1$. To make the whole graph connected, only one component must remain, so at least $K-1$ edges are necessary.

Conversely, choose one representative vertex from each connected component and connect these representatives in a chain. This uses exactly $K-1$ new edges and makes the graph connected. Therefore, the answer is $K-1$.

The number of connected components can be found with a disjoint set union data structure. Initially, every vertex is in its own set. For each input edge $(u_i,v_i)$, merge the sets containing the two endpoints. Finally, count the number of distinct representatives.

The time complexity is $O((N+M)\alpha(N))$.

Solution written by GPT5.5