minimum number of edges that should be added to an undirected graph to make it a tree Basically, it's this rosalind problem.
You're given a number of nodes and an adjacency list.
My initial guess was that the answer was the number of connected components minus 1, since by joining every connected component you would have a connected graph, and since it's stated that there are no cycles, that would be a tree.
Why is this approach wrong? The real answer is just the number of nodes-1-number of edges, which I understand, but can't see how is this not equivalent to my answer.
Also, the sample dataset given bugs me. I see three connected components so I don't see why the answer is not 2.
Bear in mind, i'm almost new to graph theory so i'm sorry if i'm missing something simple.
Your first guess is correct. Sometimes there is more than one way to write the same solution.
Clearly, if there are $k$ connected components you'll need exactly $k-1$ edges to connect them (without forming any cycle).
On the other hand, a tree with $n$ nodes must have exactly $n-1$ edges, so if the graph is acyclic and already has $m$ edges, then it is missing $n-1-m$ edges.
Regarding the example: the given graph has $n=10$ vertices, $m=6$ edges, and $k=4$ connected components (not 3), so the answer is $3=k-1=n-m-1$. The sets of vertices in each connected component are $\{1,2,8\}, \{3\}, \{4, 6, 10\}$, and $\{5, 7, 9\}$.