Number of Operations to Make Network Connected
MedPrompt
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 are given an initial computer network connections. 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.
Example 1:
Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.Example 2:
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2Example 3:
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output: -1
Explanation: There are not enough cables.
Constraints:
1 <= n <= 1051 <= connections.length <= min(n * (n - 1) / 2, 105)connections[i].length == 20 <= ai, bi < nai != bi- There are no repeated connections.
- No two computers are connected by more than one cable.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the network as a graph and uses a standard graph traversal algorithm, like Depth-First Search (DFS), to solve the problem. The core idea is that to connect k separate components of a graph, we need k - 1 connections. The problem thus reduces to finding the number of connected components in the initial network. A prerequisite is having enough cables; a network with n computers needs at least n - 1 cables to be connected. If this condition isn't met, it's impossible to connect the network.
Algorithm
- Check if
connections.length < n - 1. If true, return -1. - Build an adjacency list
adjfrom theconnectionsarray to represent the computer network. - Initialize a boolean array
visitedof sizento allfalse. - Initialize a counter
componentsto 0. - Loop through each computer
ifrom 0 ton-1:- If
visited[i]isfalse:- Increment
components. - Call a DFS function starting from
ito traverse the component and mark all its nodes as visited.
- Increment
- If
- Return
components - 1.
Walkthrough
First, we perform a quick check: if the number of available cables (connections.length) is less than n - 1, we cannot connect all n computers, so we return -1. Otherwise, a solution is always possible.
We then proceed to count the number of connected components. To do this, we build an adjacency list representation of the graph. We also use a visited array to keep track of computers we have already visited. We iterate through each computer from 0 to n-1. If a computer hasn't been visited, it means we've found a new, unexplored connected component. We increment our component counter and start a DFS traversal from this computer. The DFS will explore all reachable computers from this starting point, marking them as visited. After iterating through all computers, the counter will hold the total number of connected components.
The minimum number of operations (cable moves) required is this count minus one.
Here is a Java implementation of this approach:
import java.util.ArrayList;import java.util.List; class Solution { public int makeConnected(int n, int[][] connections) { if (connections.length < n - 1) { return -1; } List<Integer>[] adj = new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); } for (int[] conn : connections) { adj[conn[0]].add(conn[1]); adj[conn[1]].add(conn[0]); } boolean[] visited = new boolean[n]; int components = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { dfs(i, adj, visited); components++; } } return components - 1; } private void dfs(int u, List<Integer>[] adj, boolean[] visited) { visited[u] = true; for (int v : adj[u]) { if (!visited[v]) { dfs(v, adj, visited); } } }}Complexity
Time
O(n + E), where `n` is the number of computers and `E` is the number of connections. Building the adjacency list takes O(E) time. The DFS traversal visits each vertex and edge once, resulting in O(n + E) time.
Space
O(n + E). The adjacency list requires O(n + E) space. The `visited` array requires O(n) space, and the recursion stack for DFS can go up to O(n) in the worst case.
Trade-offs
Pros
Intuitive approach based on standard graph traversal.
Relatively easy to implement if familiar with DFS/BFS.
Cons
Requires more space than the Union-Find approach due to the storage of the adjacency list.
Solutions
Solution
class Solution {private int[] p;public int makeConnected(int n, int[][] connections) { p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } int cnt = 0; for (int[] e : connections) { int a = e[0]; int b = e[1]; if (find(a) == find(b)) { ++cnt; } else { p[find(a)] = find(b); --n; } } return n - 1 > cnt ? -1 : n - 1; }private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.