Completing a Tree

In this problem we are asked to find out the minimum number of edges we need to add to a graph of n nodes described by a given adjacency list in order to produce a tree. I quite quickly managed to overthink the problem and got caught up trying to build the graphs described by the adjacency list, until I finally realised there is a much simpler solution.

Sample dataset:

10

1 2

2 8

4 10

5 9

6 10

7 9

Expected output:

3

The key to this problem is to realise that a tree with n nodes contains n-1 edges. If we then look at the adjacency list, every element of this list represents a node. Thus, to obtain the number of nodes needed to produce a tree, we simply need to make the calculation n-1-elements in the list. The following Python code does just that:

data = []                                          

with open('sampledata.txt', 'r') as f:             

    for line in f:                                 

        split_data = [int(x) for x in line.split()]

        data.append(split_data)                    

n = data[0][0]                                     

edges = data[1:]                                   

print(n - len(edges) - 1)