Edges to Make Connected

Problem

Compute the minimum number of new undirected edges needed to connect the whole graph.

Count the connected components c of the given edge list, then the answer is c - 1 because each added edge can merge two components. edges is a list of [u, v] pairs. A graph with n <= 1 is already connected and needs 0 edges.

Hint

One new edge drops the component count by exactly one, so c - 1 edges always suffice.

Test cases

case 1

in: [4,[[0,1],[2,3]]]

expected: 1

case 2

in: [5,[]]

expected: 4

case 3

in: [3,[[0,1],[1,2]]]

expected: 0

case 4

in: [1,[]]

expected: 0

case 5

in: [6,[[0,1],[2,3],[4,5]]]

expected: 2

Starter codePython

def edges_to_make_connected(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor