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

Number of Operations to Make Network Connected

Medium GraphBFSDFS LeetCode

Given n computers and connections, return the minimum number of cable moves to connect all computers. Return -1 if impossible.

Example: n=4, connections=[[0,1],[0,2],[1,2]] → Output: 1

Sample Input
—
Sample Output
—
Constraints
  • 1 <= n <= 10^5
  • 1 <= connections.length <= min(n*(n-1)/2, 10^5)
Test Cases
Case 1
Args: [4,[[0,1],[0,2],[1,2]]] Expected: 1
Topics
GraphBFSDFS

Union-Find (Count Components)

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

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

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

Saved in this browser only. Private to you.

JavaScript