Number of Operations to Make Network Connected

Explanation & Solution

Description

There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network 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 can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected.

Return the minimum number of times you need to do this in order to make all the computers connected. If it is not possible, return -1.

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

Output: 1

Explanation: Remove cable between 0 and 2, place between 2 and 3.

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
There are no repeated connections

Approach

Union Find pattern

1. Check Minimum Cable Requirement

We need at least n - 1 cables to connect n computers
If connections.length < n - 1, return -1 immediately

2. Initialize Union Find

Create parent and rank arrays for n nodes
Each computer starts as its own component

3. Union All Connected Computers

For each connection [a, b], union computers a and b
Redundant connections (where a and b are already connected) become spare cables

4. Count Connected Components

Count nodes that are their own root (i.e., find(i) === i)
Each distinct root represents a separate connected component

5. Return Components - 1

To connect k components, we need k - 1 cable operations
Since we verified enough total cables exist, these operations are always possible

Key Insight

If we have enough cables (≥ n-1), the answer is simply the number of components minus 1
Redundant cables within components can always be repurposed to bridge separate components

Time

**O(n + m · α(n))** where m is the number of connections

Space

O(n)

Visualization

Input:

BFS Traversal4 nodes, 3 edges

output—

Press play to start bfs traversal

CurrentQueuedVisited

9 steps

Solution Code

Minimize Malware Spread