← DSA Atlas
Dedicated problem page · #1319

Number of Operations to Make Network Connected

MediumUnion-Find / Disjoint Set UnionCount components, connect with spare edgesUnion-Find (Disjoint Set Union)
Solve on LeetCode ↗
1319
MediumUnion-Find / Disjoint Set UnionUnion-Find (Disjoint Set Union)Count components, connect with spare edges

Number of Operations to Make Network Connected

There are n computers numbered 0 to n-1 connected by ethernet cables; connections[i] = [a, b] means computers a and b are directly connected. You may unplug any existing cable and plug it between any two computers. Return the minimum number of such moves to make every computer connected to every other (one single network), or -1 if it is impossible.

Open official problem prompt ↗
In plain English

Find the fewest cable relocations that turn a partially connected set of computers into one fully connected network, or prove it cannot be done.

Picture it like this

Think of islands joined by bridges. If you already have enough bridge material, every extra bridge inside an island can be lifted and dropped between two islands; you need exactly one relocation per gap between separate island groups.

Example
Input
n = 4, connections = [[0,1],[0,2],[1,2]]
Output
1
Why
Computers 0,1,2 are already one component and computer 3 is alone; one of the three cables among {0,1,2} is redundant and can be moved to link computer 3.
Constraints
1 <= n <= 10^51 <= connections.length <= min(n*(n-1)/2, 10^5)connections[i].length == 20 <= a_i, b_i < na_i != b_iThere are no repeated connectionsNo two computers are connected by more than one cable
Pattern lesson

See the pattern, then code

Count components, connect with spare edges
Recognition clue

You are asked whether a set of nodes can be fully linked and by how much, and edges can be freely relocated -- that is a connectivity / connected-components question, the signature use of Union-Find.

↗
Union-Find / Disjoint Set Union

Dynamic connectivity, merging groups, redundant edges, or Kruskal's algorithm.. Connecting n nodes into one network needs at least n-1 cables. If you have fewer, it is impossible. If you have at least n-1, any cable beyond a spanning structure is redundant and can be relocated, and exactly (components - 1) relocations are needed to fuse all components into one.

New words, made simpleKnow these before the algorithm
Connected component
A maximal group of computers that can all reach each other through cables
Redundant edge
A cable joining two computers already in the same component; removing it does not split the component
Union-Find / DSU
A structure that tracks which set each element belongs to and merges sets in near-constant time
Spanning connectivity
The minimum n-1 edges needed to keep n nodes in one piece
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Repeated BFS/DFS flood fill

Correct and linear, but building the adjacency list and traversing is heavier than needed; DSU answers connectivity more directly with less bookkeeping.

Build an adjacency list, then run a traversal from every unvisited node to count connected components

Time O(n + E)Space O(n + E)
Best choiceUnion-Find on the edges

Minimal memory, near-linear, and the merge counter gives the component count for free -- the cleanest fit.

Reject early if there are fewer than n-1 cables, then union each connection's endpoints while counting components; the answer is components - 1

Time O(E * alpha(n))Space O(n)
The rule we keep true

Invariant

The component counter always equals the number of distinct connected groups among the computers processed so far; it decreases by exactly one on each successful union.

Why this is correct

Reasoning

A single network of n nodes requires at least n-1 edges, so fewer means -1. When there are enough edges, every component beyond the first must be attached by one relocation, and redundant edges (unions that find the two endpoints already merged) are exactly the surplus cables available to relocate. With c components, c-1 relocations both suffice and are necessary.

The algorithm in three movesSay these aloud before coding
1If connections.length < n-1, return -1 immediately (too few cables)

edges = 3 >= n-1 = 3, feasible

2Initialize DSU with each computer its own component and a counter = n

after unions: {0,1,2}, {3} -> components = 2

3Union the two endpoints of every connection, decrementing the counter on each successful merge

answer = 2 - 1 = 1

4Return components - 1, the number of merges still needed

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
22
33
1 · Read3 connections, n = 4
2 · AskIs len(connections) >= n-1?
3 · Update state3 >= 3
4 · ResultFeasible; continue
Key takeaway

Nodes 0-2 form one component while node 3 (highlighted) is isolated, needing one relocated cable.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Early impossibility check

    With fewer than n-1 cables you can never span all n computers, so return -1 before doing any work.

  2. 2
    Lines 5-11DSU with path compression

    parent[x] points toward a set representative; find flattens the chain as it climbs, keeping operations near O(1) amortized.

  3. 3
    Lines 13-18Union each connection and count

    Start with n components; every successful merge of two different roots reduces the count by one. Redundant edges leave the count unchanged.

  4. 4
    Lines 19Return relocations needed

    Fusing c components into one takes c-1 moves, and the surplus cables guaranteed by the feasibility check supply them.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • n = 1 with no connections: already one network, answer 0
  • Exactly n-1 edges forming a tree: 1 component, answer 0
  • Fewer than n-1 edges: return -1
  • All computers already connected with extra redundant cables: answer 0
!

Common beginner mistakes

  • Forgetting the len(connections) < n-1 early return and producing a wrong non-negative answer
  • Counting redundant edges as merges, corrupting the component count
  • Returning the component count instead of components - 1
  • Recursive find without path compression risking deep recursion / TLE on n up to 10^5
Check your understanding

If n = 5 and there are 6 connections forming components {0,1}, {2,3}, {4}, what is the answer and why?

More in Union-Find / Disjoint Set Union

#684Redundant ConnectionCycle detection while building#305Number of Islands IIIncremental connectivity#721Accounts MergeMerge by shared key#947Most Stones Removed with Same Row or ColumnConnected components, keep one per group#952Largest Component Size by Common FactorUnion by prime factors#990Satisfiability of Equality EquationsEquality classes then contradiction check