There are n computers numbered 0 to n-1 connected by cables. connections[i] = [a, b] means a cable connects computers a and b. You can remove an existing cable and place it between any pair of disconnected computers. Return the minimum number of such operations to make all computers connected, or -1 if impossible.

Examples

Example 1:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation:
  0             0
  |\      →     |
  1-2    3     1-2-3
  Redundant cable (1,2) can connect node 3.

Example 2:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2

Example 3:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output: -1
Explanation: Not enough cables (need at least 5 for 6 computers).

Constraints

  • 1 <= n <= 10^5
  • 1 <= connections.length <= min(n*(n-1)/2, 10^5)
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] < n
  • No repeated connections, no self-loops

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
BFS / DFS traversal (this problem) O(V+E) O(V) Connectivity, flood fill
Dijkstra O((V+E)log V) O(V) Non-negative edge weights
Union-Find (DSU) O(α(n)) O(n) Dynamic connectivity
Topological sort O(V+E) O(V) DAG ordering, cycle detection

Thinking Process

Key Insight 1: Minimum Cables

To connect n nodes, we need at least n - 1 edges. If connections.size() < n - 1, it’s impossible – return -1.

Key Insight 2: Connected Components

If we have enough cables, any redundant cable (within an already-connected component) can be repositioned to bridge two disconnected components.

The answer is simply:

$text{operations} = text{components} - 1

Each operation connects one more component to the rest.

Why DSU?

Every connection merges two computers. Start with n components, and each successful union reduces the count by one. After processing all connections, the remaining component count gives the answer directly.

Graph BFS layers S a b t BFS: expand by layers (queue)

Approach: DSU – O(n + m)$

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
# Graph:  0    3
#         |\   (isolated)
#         1-2
# One cable is redundant among 0,1,2. We can move it to connect 3.
# Answer = 1.

Solution Explanation

Approach: BFS / DFS traversal (this problem)

Key idea: ### Key Insight 1: Minimum Cables

Walkthrough — input n = 4, connections = [[0,1],[0,2],[1,2]], expected output 1:

0 0 |\ → | 1-2 3 1-2-3 Redundant cable (1,2) can connect node 3.

Walk-Through: n=4, connections=[[0,1],[0,2],[1,2]]

Start: components = 4  (each node is its own component)

unite(0,1) → success → components = 3
unite(0,2) → success → components = 2
unite(1,2) → 1 and 2 already connected → skip (redundant cable)

components - 1 = 2 - 1 = 1 ✓

Common Mistakes

  • Forgetting the n - 1 edge check upfront (without enough cables, no amount of rearranging helps)
  • Counting redundant edges instead of components (the answer is components - 1, not the number of extra cables)

Key Takeaways

  • “Enough cables?” check: m >= n - 1 is necessary and sufficient (given we can reposition)
  • Components - 1 is the universal formula for “minimum operations to connect all components”
  • DSU naturally tracks component count: start at n, decrement on each successful union

References

Template Reference