I trying to solve the following problem in $O(n^2)$:
We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to make the graph connected - you can travel by road to each city?
Basically, at the start, we have just the vertices. As we read the textfile, we add a new edge each time we read a new line and we should decide after how many edges added is our graph now connected.
An example: An example: we have 5 vertices, A, B, C, D, E. In the textfile, we have defined these edges: A-B, B-C, A-C, B-D, C-D, A-D, B-E, C-E. The graph have been made connected after building 7 edges, while we have only 5 vertices when we start (5 components).
I solved it the following way: I'm calling the BFS algorithm after adding each edge to the graph until the graph is connected and counting the number of BFS calls. However, since the BFS itself has a time complexity of $O(n^2)$ and I'm calling it n-times, I have a worstcase time complexity near $O(n^3)$.
How would I solve this issue in $O(n^2)$?