Fastest algorithm for connectivity problem
If I understand you correctly, you want to maximize the number of pairs of vertices that are connected.
In a connected (undirected) graph, all vertices are reachable from each other, so the number is always $n^2$.
You can always connect to components with an edge by placing it arbitrarily between the components, and this will increase the number from $a^2 + b^2 \leq (a+b)^2$ to $(a+b)^2$.
If $a \geq b \geq c$, then
$$(a + b)^2 - a^2 - b^2 \geq \max((b+c)^2 - b^2 - c^2 , (a+c)^2 - a^2 - c^2).$$
It follows that the optimal solution is to iteratively connect the two largest components in your graph, which corresponds to, given $k$ edges, connecting the $k+1$ largest components of your graph.
Finding the $k+1$ largest components can be done in $O(n+m)$ time.