Make Network Connected

Given n computers and a list of cables, return the minimum number of cable moves needed to make the whole network connected. Each move can repurpose one spare edge. DSU union operations help count the final number of components and determine whether enough spare cables exist.

Input Format

n = number of computers, connections = available cables

Output Format

minimum number of cable moves needed

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

n = 4
connections = [[0,1],[0,2],[1,2]]

Output:

1

Explanation:

There are two components: {0,1,2} and {3}. One spare cable can connect them.

Example 2:

Input:

n = 6
connections = [[0,1],[0,2],[0,3],[1,2]]

Output:

-1

Explanation:

Three components remain, so two moves are needed.

Example 3:

Input:

n = 4
connections = [[0,1],[2,3]]

Output:

-1

Explanation:

Only two cables exist, which is not enough to connect 4 computers.

Loading...
Make Network Connected - Union Find DSA Problem