Let's say we have been given the number of nodes and edges, N and M respectively. And then we are given which of the nodes are connected.How do we find the minimum amount of extra edge(s) needed to complete the connection, so that you can visit every node? By finding the answer you should be able to traverse to every node, by either going directly or going through another node to get to the goal.
Example on input:
4 2 (Nodes and edges)
0 1 (node 0 and node 1 is connected)
2 3 (node 2 and node 3 is connected)
Which then should give us the answer 1, we need one extra edge to complete the connection.
All that you need is:
1) Find connected components. It can be done by dfs or bfs. In your example these components are 0, 1 and 2, 3 respectively.
2) Then you need to iterate through the all components and connect any two vertexes for every two consequtive components. In this way you connect first and second components, then second and third components and so on... In your example you can connect any of vertexes 0, 1 with any of vertexes 2, 3. For example, you can connect vertexes 0 and 2.
It's easy to see that if the total number of components is equal to C then the answer will be C - 1 additional edges.