Number of Operations to Make Network Connected

Number of Operations to Make Network Connected medium

Description

There are n computers numbered from 0 to n - 1 connected by ethernet cables connections, where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network.

You are given an initial computer network connections. You can extract certain cables between two directly connected computers and place them between any two computers to make all the computers connected. Return the minimum number of times you need to do this. If it is not possible, return -1.

Examples

> Case 1:
    n = 4, connections = [[0,1],[0,2],[1,2]]
    Output: 1
    Explanation: Remove cable between 1-2 (redundant), connect 3.
 
> Case 2:
    n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
    Output: 2
 
> Case 3:
    n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
    Output: -1
    Explanation: Not enough cables (need at least n-1 = 5, have only 4).

Constraints

1 <= n <= 10^5
1 <= connections.length <= min(n × (n - 1) / 2, 10^5)
connections[i].length == 2
0 <= ai, bi < n
ai != bi
No repeated connections.

State design / Intuition

Two key observations:

Minimum cables needed: to connect k disconnected components into one, you need exactly k − 1 cables (each cable merge reduces the component count by 1).
Available spare cables: count redundant connections — edges that connect nodes already in the same component. Each such edge is a “spare cable” you can move.

If spare_cables >= components - 1, it’s possible in exactly components - 1 moves. Otherwise return -1.

The check len(connections) >= n - 1 is a quick lower bound: with fewer than n - 1 edges, you can never connect n nodes regardless of placement.

Code

The early check len(connections) < n - 1 is key: a connected graph on n nodes needs at least n − 1 edges. If we have fewer total edges, it’s impossible regardless of how we rearrange them — return -1 immediately.

Analysis

Time: O(E α(V)) ≈ O(E).
Space: O(V).

Same skin

Redundant Connection — same union-find, return the first redundant edge instead of counting.
Number of Connected Components (LC 323) — same component-counting logic.
Minimum Number of Edges to Connect All Nodes — same observation: need components - 1 edges.
Graph Valid Tree — components == 1 and spare == 0.

Redundant Connection Remove Max Edges