Number of Operations to Make Network Connected Medium 0 attempts
LeetCode ↗

Number of Operations to Make Network Connected

Medium GraphBFSDFS LeetCode

There are n computers labeled from 0 to n - 1, linked by a set of direct network cables given in connections. You can pull out any existing cable and use it to join two computers that aren't yet connected. Determine the minimum number of such moves needed to make the whole network reachable from any computer to any other — or return -1 if there aren't enough cables to make that possible.

Input Format
Implement makeConnected(n, connections). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
n = 1
connections = []
Output
0
Constraints
  • 1 <= n <= 10^5
  • 0 <= connections.length <= min(n*(n-1)/2,10^5)
  • Connections are distinct undirected edges between different computers.
Test Cases (2)
Case 1
Args: [4,[[0,1],[0,2],[1,2]]] Expected: 1
Case 2
Args: [1,[]] Expected: 0
Topics
GraphBFSDFS

Union-Find (Count Components)

Need at least n-1 edges. Extra edges = total - (n - components). Answer = components - 1.

javascript
function makeConnected(n, connections) {
  if (connections.length < n - 1) return -1;
  const parent = Array.from({length: n}, (_, i) => i);
  const size = Array(parent.length).fill(1);
  function find(x) { while(parent[x]!==x){parent[x]=parent[parent[x]];x=parent[x];}return x; }
  function union(a,b) { a=find(a);b=find(b);if(a===b)return;if(size[a]<size[b])[a,b]=[b,a];parent[b]=a;size[a]+=size[b]; }
  let components = n;
  for (const [a, b] of connections) {
    const pa = find(a), pb = find(b);
    if (pa !== pb) { union(pa,pb); components--; }
  }
  return components - 1;
}

Time: O(E α(n)) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript