I solved the following problem:

We have vertices which represents cities and a textfile with edges between vertices representing roads. How many roads do we need to build to make the graph connected – you can travel by road to each city?

Using the BFS algorithm. Basically, 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)?

Thanks!