396. Edges Needed to Join It All Up
Print the smallest number of edges that must be added to make the whole graph connected.
The answer is short: count the components, and subtract one. Each new edge can
join at most two components into one, so c components need at least c - 1
edges, and c - 1 is always enough because you can chain them together in any
order.
The reasoning matters more than the code here, which is problem 363 with one subtraction. What is worth taking away is that the number of EDGES already present does not enter into it at all. A triangle and a path both count as one component.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
edges. Each of the next m lines contains two integers u and v, an
undirected edge between those vertices. Vertices are numbered 1 to n.
Output
Print one integer, the number of edges that must be added.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.