Problem Statement:
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:
- To connect all
ncomputers, at least n - 1 connections are required. If not,return -1. - Build an
undirected graphusing the given connections. - Use BFS to traverse the graph and count the number of connected components.
- Each BFS call marks all nodes in one component as visited.
- If there are k connected components, we need
k - 1extra connections to connect them all. - Return
noOfComponents - 1.
Time & Space Complexity:
Time Complexity: O(V + E)
Space Complexity: O(V + E)
Dry Run
Input: n = 5, connections = [[0,1],[0,2],[3,4]]
Step 0: Start Function: makeConnected(5, connections) connections.length = 3 n - 1 = 4 connections.length < n - 1 โ false (so continue) Step 1: Build Graph (Adjacency List) graph = [ [1, 2], // 0 [0], // 1 [0], // 2 [4], // 3 [3] // 4 ] visited = [false, false, false, false, false] noOfComponents = 0 Step 2: Traverse Nodes (for loop) i = 0: - visited[0] = false - noOfComponents = 1 - Call bfs(0) BFS starting from node 0: Queue = [0] visited = [true, false, false, false, false] Pop 0: - Neighbor 1 โ mark visited, push to queue - Neighbor 2 โ mark visited, push to queue Queue = [1, 2] visited = [true, true, true, false, false] Pop 1: - Neighbor 0 already visited Pop 2: - Neighbor 0 already visited BFS ends for component starting at 0 i = 1: - visited[1] = true โ skip i = 2: - visited[2] = true โ skip i = 3: - visited[3] = false - noOfComponents = 2 - Call bfs(3) BFS starting from node 3: Queue = [3] visited = [true, true, true, true, false] Pop 3: - Neighbor 4 โ mark visited, push to queue Queue = [4] visited = [true, true, true, true, true] Pop 4: - Neighbor 3 already visited BFS ends for component starting at 3 i = 4: - visited[4] = true โ skip Step 3: End Total Components = 2 Required Operations = noOfComponents - 1 = 2 - 1 = 1
Output: 1
var makeConnected = function(n, connections) {
if (connections.length < n - 1) return -1;
let graph = Array.from({ length: n }, () => []);
for (let [from, to] of connections) {
graph[from].push(to);
graph[to].push(from);
}
let visited = new Array(n).fill(false);
let noOfComponents = 0;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
noOfComponents++;
bfs(i, visited, graph);
}
}
return noOfComponents - 1;
};
function bfs(src, visited, graph) {
let q = [src];
visited[src] = true;
while (q.length) {
let curr = q.shift();
for (let neighbor of graph[curr]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
from collections import deque
def makeConnected(n, connections):
if len(connections) < n - 1:
return -1
graph = [[] for _ in range(n)]
for u, v in connections:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
components = 0
def bfs(src):
q = deque([src])
visited[src] = True
while q:
curr = q.popleft()
for neighbor in graph[curr]:
if not visited[neighbor]:
visited[neighbor] = True
q.append(neighbor)
for i in range(n):
if not visited[i]:
components += 1
bfs(i)
return components - 1
import java.util.*;
class Solution {
public int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) return -1;
List> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] edge : connections) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
components++;
bfs(i, graph, visited);
}
}
return components - 1;
}
private void bfs(int src, List> graph, boolean[] visited) {
Queue q = new LinkedList<>();
q.add(src);
visited[src] = true;
while (!q.isEmpty()) {
int curr = q.poll();
for (int neighbor : graph.get(curr)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.add(neighbor);
}
}
}
}
}
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int makeConnected(int n, vector>& connections) {
if (connections.size() < n - 1) return -1;
vector> graph(n);
for (auto& edge : connections) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
vector visited(n, false);
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
components++;
bfs(i, graph, visited);
}
}
return components - 1;
}
void bfs(int src, vector>& graph, vector& visited) {
queue q;
q.push(src);
visited[src] = true;
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int neighbor : graph[curr]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
};
#include <stdio.h>
#include <stdlib.h>
#define MAX 100000
int visited[MAX];
int graph[MAX][MAX];
int graphSize[MAX];
void bfs(int src, int n) {
int queue[MAX], front = 0, rear = 0;
queue[rear++] = src;
visited[src] = 1;
while (front < rear) {
int curr = queue[front++];
for (int i = 0; i < graphSize[curr]; i++) {
int neighbor = graph[curr][i];
if (!visited[neighbor]) {
visited[neighbor] = 1;
queue[rear++] = neighbor;
}
}
}
}
int makeConnected(int n, int connections[][2], int size) {
if (size < n - 1) return -1;
for (int i = 0; i < n; i++) {
visited[i] = 0;
graphSize[i] = 0;
}
for (int i = 0; i < size; i++) {
int u = connections[i][0];
int v = connections[i][1];
graph[u][graphSize[u]++] = v;
graph[v][graphSize[v]++] = u;
}
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
components++;
bfs(i, n);
}
}
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[] graph = new List[n];
for (int i = 0; i < n; i++) graph[i] = new List();
foreach (var edge in connections) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
bool[] visited = new bool[n];
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
components++;
BFS(i, graph, visited);
}
}
return components - 1;
}
private void BFS(int src, List[] graph, bool[] visited) {
Queue q = new Queue();
q.Enqueue(src);
visited[src] = true;
while (q.Count > 0) {
int curr = q.Dequeue();
foreach (int neighbor in graph[curr]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.Enqueue(neighbor);
}
}
}
}
}
1 Comment
Finding the cheapest flight with K stops often comes down to flexibility and smart search strategies. Allowing one or two stopovers can significantly reduce ticket prices compared to direct flights, especially on long routes. Using flexible date searches, comparing multiple airlines, and booking during off-peak hours can also help uncover better deals.
Sometimes a slightly longer journey can mean big savings, so itโs all about balancing cost, time, and comfort.
If you like practical online tools, hereโs an Arabic age calculator that works with Hijri dates:
ุญุณุงุจ ุงูุนู ุฑ ุจุงููุฌุฑู