This problem asks:

Given: A positive integer n (n≤1000) and an adjacency list corresponding to a graph on n nodes that contains no cycles.

Return: The minimum number of edges that can be added to the graph to produce a tree.

Required reading

  1. Graph theory
  2. Graph connectivity
  3. Tree
  4. Internal node
  5. Graph cycles
  6. Shouryanpatil’s code for completing a tree

Restate the problem

I’m going to get a number n less than 1,000, and a list of all the edges of a graph with n nodes. There are no graph cycles in the list of edges. The graph with n nodes is incomplete, meaning that there is no path that connects every node with every other node. I need to return the smallest number of edges that can be added to complete the graph.

Solution steps

First, I struggled to think of how I could possibly make any progress on this until I read Shouryanpatil’s code and realized that nothing about the specific edges given in the problem matter at all. The only relevant fact is that the number of edges on a tree with n vertices is always n-1.

I wrote a function to count the number of edges, subtracted from the number of vertices and got the correct result on my first submission.