Number of Operations to Make Network Connected solution and explanation
IBM
Google
9 more videos on this problem
G-49. Number of Operations to Make Network Connected - DSUtake U forward · 14:48 · 177K views
Number of Operations to Make Network Connected - (AMAZON) | Graph Concepts & Qns - 22 | Coding LivecodestorywithMIK · 20:28 · 23K views
Number of Operations to Make Network Connected | Leetcode #1319 | MST | DFSTechdose · 21:40 · 17K views
Leetcode 1319: Number of Operations to Make Network ConnectedAlgorithms Casts · 23:57 · 1K views
Leetcode #1319. Number of Operations to Make Network Connected [LeetCode with AlgoTips]AlgoTips · 11:58 · 1K views
Daily Leetcode #1087: Mar 23, 2023 - 1319. Number of Operations to Make Network ConnectedProgramming Live with Larry · 6:01 · 855 views
1319. Number of Operations to Make Network Connected | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 14:17 · 713 views
LeetCode 1319 - Number of Operations to Make Network Connected [Daily Challenge]Code with Carter · 15:48 · 532 views
Number of Operations to Make Network Connected - Leetcode 1319 - PythonLit Code · 6:16 · 377 views
Leetcode #1319 || Number of Operations to Make Network Connected || DSU || JAVACode Unraveled · 15:41 · 367 views
The problem
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: 2
Example 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.
Approach overview
Problem Overview: You are given n computers and a list of cable connections between them. Each cable connects two computers. The goal is to determine the minimum number of operations needed to connect the entire network so every computer can reach every other computer. If there are not enough cables to achieve this, return -1.
The key observation: a connected network of n nodes needs at least n-1 edges. If the number of cables is less than that, building a fully connected network is impossible regardless of rearrangement.
Approach 1: Union-Find to Determine Connected Components (Time: O(n + m * α(n)), Space: O(n))
This approach models the computers as nodes in a graph. Use the Union-Find (Disjoint Set Union) data structure to merge computers that are already connected by cables. Iterate through each connection and perform union(a, b). If both computers already share the same root, that cable is redundant and can be reused elsewhere. After processing all edges, count the number of unique connected components. To connect k components, you need k - 1 cables. If the number of redundant cables is at least k - 1, the network can be connected with that many operations; otherwise return -1. Path compression and union by rank keep operations nearly constant time.
Approach 2: Depth-First Search (DFS) Approach (Time: O(n + m), Space: O(n + m))
This approach explicitly explores the network using graph traversal. First build an adjacency list from the connections. Then iterate through all computers and run Depth-First Search from each unvisited node to mark its entire component. Each DFS traversal identifies one connected component. After counting components, compute the number of operations required as components - 1. Before doing this, check whether the total number of cables is at least n - 1; otherwise return -1. DFS works well because the problem reduces to counting how many isolated groups exist in the graph.
Recommended for interviews: The Union-Find approach is typically preferred. It directly tracks connectivity while efficiently detecting redundant edges. Interviewers often expect candidates to recognize that the task is essentially counting connected components in a graph and that extra edges can be repurposed. Implementing DFS demonstrates solid graph fundamentals, but Union-Find shows stronger familiarity with connectivity problems commonly seen in distributed systems and network modeling.
Approach 1: Union-Find to Determine Connected Components
This approach uses the Union-Find (or Disjoint Set Union, DSU) data structure. It helps in efficiently finding the number of connected components in the network. Initially, every computer is its own component. We then iterate over each connection and unite the components of the two connected computers. Finally, we count how many separate components remain, since that will determine the number of cables needed to connect them.
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
if len(connections) < n - 1:
return -1
parent = list(range(n))
rank = [0] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
rootX, rootY = find(x), find(y)
if rootX != rootY:
if rank[rootX] < rank[rootY]:
parent[rootX] = rootY
elif rank[rootX] > rank[rootY]:
parent[rootY] = rootX
else:
parent[rootY] = rootX
rank[rootX] += 1
for a, b in connections:
union(a, b)
components = len({find(i) for i in range(n)})
return components - 1class Solution {
public int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) return -1;
int[] parent = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; ++i) parent[i] = i;
for (int[] conn : connections) {
union(parent, rank, conn[0], conn[1]);
}
int components = 0;
for (int i = 0; i < n; ++i) {
if (find(parent, i) == i) components++;
}
return components - 1;
}
private int find(int[] parent, int i) {
if (parent[i] != i) {
parent[i] = find(parent, parent[i]);
}
return parent[i];
}
private void union(int[] parent, int[] rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY])
parent[rootX] = rootY;
else if (rank[rootX] > rank[rootY])
parent[rootY] = rootX;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}#include <vector>
class Solution {
public:
int find(std::vector<int>& parent, int i) {
if (parent[i] == i) return i;
return parent[i] = find(parent, parent[i]);
}
void union_sets(std::vector<int>& parent, std::vector<int>& rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY])
parent[rootX] = rootY;
else if (rank[rootX] > rank[rootY])
parent[rootY] = rootX;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
int makeConnected(int n, std::vector<std::vector<int>>& connections) {
if (connections.size() < n - 1) return -1;
std::vector<int> parent(n), rank(n, 0);
for (int i = 0; i < n; ++i) parent[i] = i;
for (const auto& conn : connections) {
union_sets(parent, rank, conn[0], conn[1]);
}
int components = 0;
for (int i = 0; i < n; ++i) {
if (find(parent, i) == i) components++;
}
return components - 1;
}
};var makeConnected = function(n, connections) {
if (connections.length < n - 1) return -1;
const parent = Array.from({ length: n }, (_, i) => i);
const rank = Array(n).fill(0);
const find = (x) => {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
};
const union = (x, y) => {
const rootX = find(x);
const rootY = find(y);
if (rootX !== rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX] += 1;
}
}
};
connections.forEach(([a, b]) => union(a, b));
const components = new Set(parent.map((_, i) => find(i))).size;
return components - 1;
};#include <stdio.h>
#include <stdlib.h>
int find(int* parent, int i) {
if (parent[i] == i)
return i;
return parent[i] = find(parent, parent[i]);
}
void union_sets(int* parent, int* rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY])
parent[rootX] = rootY;
else if (rank[rootX] > rank[rootY])
parent[rootY] = rootX;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
int makeConnected(int n, int** connections, int connectionsSize, int* connectionsColSize) {
if (connectionsSize < n - 1)
return -1;
int* parent = (int*)malloc(n * sizeof(int));
int* rank = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
for (int i = 0; i < connectionsSize; i++) {
union_sets(parent, rank, connections[i][0], connections[i][1]);
}
int components = 0;
for (int i = 0; i < n; i++) {
if (find(parent, i) == i)
components++;
}
free(parent);
free(rank);
return components - 1;
}public class Solution {
public int MakeConnected(int n, int[][] connections) {
if (connections.Length < n - 1) return -1;
int[] parent = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
foreach (var conn in connections) {
Union(parent, rank, conn[0], conn[1]);
}
int components = 0;
for (int i = 0; i < n; i++) {
if (Find(parent, i) == i) components++;
}
return components - 1;
}
private int Find(int[] parent, int i) {
if (parent[i] != i) {
parent[i] = Find(parent, parent[i]);
}
return parent[i];
}
private void Union(int[] parent, int[] rank, int x, int y) {
int rootX = Find(parent, x);
int rootY = Find(parent, y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}This Python solution focuses on employing the Union-Find with path compression and union by rank. We iteratively unite connected components and identify the number of disjoint sets remaining. The result is the count of operations needed, calculated by subtracting one from the number of components.
Time Complexity: O(n + m), where n is the number of computers and m is the number of connections. Space Complexity: O(n).
Approach 2: Depth-First Search (DFS) Approach
In this approach, we consider the computers and connections as a graph and use Depth-First Search (DFS) to determine the number of connected components. If there are at least n - 1 connections, it is possible to make the computers connected; otherwise, it isn't. Once the number of connected components is known, the number of operations required is the number of components minus one.
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
if len(connections) < n - 1:
return -1
graph = [[] for _ in range(n)]
for a, b in connections:
graph[a].append(b)
graph[b].append(a)
visited = [False] * n
def dfs(node):
if visited[node]:
return
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(neighbor)
components = 0
for i in range(n):
if not visited[i]:
components += 1
dfs(i)
return components - 1import java.util.*;
class Solution {
public int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) return -1;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] conn : connections) {
graph.get(conn[0]).add(conn[1]);
graph.get(conn[1]).add(conn[0]);
}
boolean[] visited = new boolean[n];
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
components++;
dfs(i, visited, graph);
}
}
return components - 1;
}
private void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}
}#include <vector>
using namespace std;
class Solution {
private:
void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if (connections.size() < n - 1) return -1;
vector<vector<int>> graph(n);
for (auto& conn : connections) {
graph[conn[0]].push_back(conn[1]);
graph[conn[1]].push_back(conn[0]);
}
vector<bool> visited(n, false);
int components = 0;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(i, visited, graph);
components++;
}
}
return components - 1;
}
};var makeConnected = function(n, connections) {
if (connections.length < n - 1) return -1;
const graph = Array.from({ length: n }, () => []);
connections.forEach(([a, b]) => {
graph[a].push(b);
graph[b].push(a);
});
const visited = new Array(n).fill(false);
function dfs(node) {
if (visited[node]) return;
visited[node] = true;
for (const neighbor of graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor);
}
}
}
let components = 0;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
components++;
dfs(i);
}
}
return components - 1;
};#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
void dfs(int node, bool* visited, int** graph, int* graphColSizes, int graphSize) {
visited[node] = true;
for (int i = 0; i < graphColSizes[node]; i++) {
int neighbor = graph[node][i];
if (!visited[neighbor]) {
dfs(neighbor, visited, graph, graphColSizes, graphSize);
}
}
}
int makeConnected(int n, int** connections, int connectionsSize, int* connectionsColSize) {
if (connectionsSize < n - 1) return -1;
int* graphColSizes = (int*)calloc(n, sizeof(int));
int** graph = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; ++i) {
graph[i] = (int*)malloc(n * sizeof(int));
}
for (int i = 0; i < connectionsSize; i++) {
int a = connections[i][0], b = connections[i][1];
graph[a][graphColSizes[a]++] = b;
graph[b][graphColSizes[b]++] = a;
}
bool* visited = (bool*)calloc(n, sizeof(bool));
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, visited, graph, graphColSizes, n);
components++;
}
}
for (int i = 0; i < n; ++i) {
free(graph[i]);
}
free(graph);
free(graphColSizes);
free(visited);
return components - 1;
}using System;
using System.Collections.Generic;
public class Solution {
public int MakeConnected(int n, int[][] connections) {
if (connections.Length < n - 1) return -1;
List<List<int>> graph = new List<List<int>>();
for (int i = 0; i < n; i++) graph.Add(new List<int>());
foreach (var conn in connections) {
graph[conn[0]].Add(conn[1]);
graph[conn[1]].Add(conn[0]);
}
bool[] visited = new bool[n];
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
components++;
DFS(i, visited, graph);
}
}
return components - 1;
}
private void DFS(int node, bool[] visited, List<List<int>> graph) {
visited[node] = true;
foreach (var neighbor in graph[node]) {
if (!visited[neighbor]) {
DFS(neighbor, visited, graph);
}
}
}
}This Python solution leverages DFS to traverse and identify distinct connected components in the network. By doing so, it calculates the minimum number of operations needed by counting these components and subtracting one.
Time Complexity: O(n + c), where n is the number of computers and c is the number of connections. Space Complexity: O(n).
Approach 3: Union-Find
We can use a union-find data structure to maintain the connectivity between computers. Traverse all connections, and for each connection (a, b), if a and b are already connected, then this connection is redundant, and we increment the count of redundant connections. Otherwise, we connect a and b, and decrement the number of connected components.
Finally, if the number of connected components minus one is greater than the number of redundant connections, it means we cannot connect all computers, so we return -1. Otherwise, we return the number of connected components minus one.
The time complexity is O(m times log n), and the space complexity is O(n). Here, n and m are the number of computers and the number of connections, respectively.
function makeConnected(n: number, connections: number[][]): number {
const p: number[] = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
let cnt = 0;
for (const [a, b] of connections) {
const [pa, pb] = [find(a), find(b)];
if (pa === pb) {
++cnt;
} else {
p[pa] = pb;
--n;
}
}
return cnt >= n - 1 ? n - 1 : -1;
}func makeConnected(n int, connections [][]int) int {
p := make([]int, n)
for i := range p {
p[i] = i
}
cnt := 0
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, e := range connections {
pa, pb := find(e[0]), find(e[1])
if pa == pb {
cnt++
} else {
p[pa] = pb
n--
}
}
if n-1 > cnt {
return -1
}
return n - 1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Union-Find to Determine Connected Components | Time Complexity: O(n + m), where n is the number of computers and m is the number of connections. Space Complexity: O(n). |
| Depth-First Search (DFS) Approach | Time Complexity: O(n + c), where n is the number of computers and c is the number of connections. Space Complexity: O(n). |
| Union-Find | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find (Disjoint Set) | O(n + m * α(n)) | O(n) | Best general solution for connectivity problems and detecting redundant edges efficiently |
| Depth-First Search (DFS) | O(n + m) | O(n + m) | Useful when explicitly traversing the graph or when practicing DFS-based component counting |
Frequently asked questions
Is Number of Operations to Make Network Connected easy or hard?
The problem is classified as Medium difficulty on LeetCode. The challenge is recognizing that the network can only be connected if there are at least n - 1 cables and that the task reduces to counting connected components in a graph.
Number of Operations to Make Network Connected Python/Java solution
Python and Java implementations typically use Union-Find with path compression and union by rank. The algorithm processes each connection, merges components, counts the remaining groups, and returns components minus one if enough redundant cables exist.
How to solve Number of Operations to Make Network Connected in O(n + m)?
First check if the number of connections is at least n - 1. If not, return -1 because a connected graph needs at least that many edges. Then count connected components using either Union-Find or DFS traversal. If there are k components, the minimum operations needed to connect the network is k - 1.
What is the best approach for Number of Operations to Make Network Connected?
Union-Find (Disjoint Set Union) is the most efficient and interview-friendly approach. It quickly merges connected computers and detects redundant cables while processing edges. After building the sets, count the number of connected components and compute the required operations as components minus one. The approach runs in near linear time O(n + m * α(n)).
Is Number of Operations to Make Network Connected asked at Google/Amazon/Meta?
Graph connectivity and Union-Find problems frequently appear in interviews at companies like Google, Amazon, Meta, and Microsoft. Variations of this problem test understanding of connected components, redundant edges, and efficient graph processing.
What data structure is used in Number of Operations to Make Network Connected?
The most common data structure is Union-Find (Disjoint Set Union) to track connected components efficiently. Alternatively, the network can be represented as an adjacency list and explored using Depth-First Search or Breadth-First Search.
What is the time complexity of Number of Operations to Make Network Connected?
The optimal solution runs in O(n + m) time where n is the number of computers and m is the number of connections. Union-Find operations are effectively constant due to path compression and union by rank. DFS traversal also runs in O(n + m) because each node and edge is visited at most once.