I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the number of vertices on the longest path in the resulting connected graph. As a result I need the number of vertices on the longest simple path in the resulting graph.
For example, given a graph with the following edges:
1 0
2 0
4 3
5 3
There are multiple ways to add edges to make it a connected graph. But since I want to minimize the number of vertices on the longest path in the resulting graph, I have to add an edge between 0 and 3. Now the path with the most vertices contains 4 vertices (2 -> 0 -> 3 -> 5). If I had added an edges between 2 and 4 then the path with the most vertices would've been 1 -> 0 -> 2 -> 4 -> 3 -> 5.
Another example, given a graph with the following edges:
0 1
1 2
3 4
5 6
Here two edges need to be added: between 1 and 3 and between 3 and 5. The path with the most vertices then contains 5 vertices.
My approach was to first use DFS to identify all components. Then, for each component, I find the longest path in that component, I take the vertex that is in the middle of each of those paths and connect them. This results in one connected graph. In that resulting graph I can find the path with the most vertices. I suspect that there must be a more efficient approach to this, especially since it needs to work for a disconnected graph with at most $10^6$ vertices. Hopefully someone has a better idea on how to solve this.