If something is unclear feel free to ask

By connected components I mean components of the graph that are formed by connected nodes, therefore every node of this component is accesible within the component by a traversal.

To connect k connected blocks we need at least k-1 edges.

The request is to make an algorithm that connects all the k connected components of a graph with k-1 edges.

**The real problem is maintaining the time performance of a DFS traversal.**

O(n+m) where n are the nodes and m are the edges.

We could imagine every connected component as a node and get k nodes. This way our vertex list reduces and now what we have to do is to connect these vertexes like a linked list.

If we try to roughly do a traversal overwriting every status of the node from unexplored to visited, when we complete the traversal of a connected component, we have to go back to our vertex list and look for unexplored nodes to find another connected component. This takes another time and if we imagine this for k connected componenets we get something like O(n^2+m) as worst case could be n=k independent nodes.

Coming back to the idea of the reduced vertex list I thought to do these steps:

1. Clone the original graph, inserting inside clone's nodes references to the original ones

2. Pick up a unexplored node from the cloned list and do a traversal until its connected component gets completely visited and while visiting remove every node already visited once its edges are completely visited (BFS visit). From this connected component we should only have the first one picked up.

3. Even though we just removed a node, we still visit the others as we removed it only after passing through everyone of its edges.

4. Once done and there are no other nodes, get back to the copy of the original list where we should have only unexplored nodes. Like this we don't need to look for them as a graph could have implemented a method that removes even the reference from the vertex list, reducing automatically the vertex list size.

5. Get the reference from the previously picked up node to the original one. In the vertex copy list (clone graph) look for another unexplored node (takes literally O(1) time) and get to the original one node. Connect them in the original graph, and choose the node that we just took as "copy reference node" be the next picked up node for step 2 and now remove from this clone graph the previously picked up node. Go to step 2.

All this stuff should work but there're two conditions that I don't know if they could be tollerated:

a) Is it a good idea to clone a graph (also containing in every node references to the original nodes)?

Would it anyway take O(n+m) time?

And this one that is hardly right: O(1) time to remove a node of a graph from the vertex list, reducing even the size of the list. I don't think it's usually possible, maybe modifing the classical graph implementations but it might get bloody hard.

I think my whole solution is too complicated and almost wrong. Anyone has any better advice please?