Number of Operations to Make Network Connected

Number of Operations to Make Network Connected - 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.

Input & Output

Example 1 — Basic Network

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

› Output: 1

💡 Note: We have 4 computers. Computers 0,1,2 are connected in one group, computer 3 is isolated. We need 1 operation to connect computer 3 to any of the connected computers.

Example 2 — Not Enough Cables

$ Input: n = 6, connections = [[0,1],[0,2]]

› Output: -1

💡 Note: We have 6 computers but only 2 cables. To connect all 6 computers, we need at least 5 cables minimum. Since 2 < 5, it's impossible.

Example 3 — Already Connected

$ Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]

› Output: 2

💡 Note: We have 3 components: {0,1,2,3}, {4}, {5}. We need 2 operations to connect all components into one network.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ connections.length ≤ min(n*(n-1)/2, 10⁵)
connections[i].length == 2
0 ≤ connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
There are no repeated connections.

Visualization

Tap to expand

Understanding the Visualization

Input

n=4 computers, connections=[[0,1],[0,2],[1,2]]

Find Components

Identify separate network groups

Calculate Operations

Need components-1 operations

Key Takeaway

🎯 Key Insight: To merge k separate network components into one, you need exactly k-1 cable relocations

Asked in

M Microsoft 15 a Amazon 12 G Google 8

The key insight is that to connect k separate network components, we need exactly k-1 cables. First check if we have enough total cables (at least n-1), then count connected components using DFS or Union-Find. Best approach is Union-Find with Time: O(m × α(n)), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ DFS Component Counting	O(n + m)	O(n + m)	Use DFS to find all connected components by exploring from each unvisited computer
Union-Find (Disjoint Set)	O(m × α(n))	O(n)	Use Union-Find data structure to efficiently track connected components with path compression

DFS Component Counting — Algorithm Steps

Build adjacency list from connections
Use DFS to find connected components
Check if enough cables exist
Return components - 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from connections

DFS Traversal

Visit all nodes in each component

Count Components

Total separate groups found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void dfs(int** graph, int* graphSizes, bool* visited, int node) {
    visited[node] = true;
    for (int i = 0; i < graphSizes[node]; i++) {
        int neighbor = graph[node][i];
        if (!visited[neighbor]) {
            dfs(graph, graphSizes, visited, neighbor);
        }
    }
}

int solution(int n, int** connections, int connectionsSize) {
    // Check if we have enough cables
    if (connectionsSize < n - 1) {
        return -1;
    }
    
    // Build adjacency list
    int** graph = (int**)malloc(n * sizeof(int*));
    int* graphSizes = (int*)calloc(n, sizeof(int));
    
    // First pass: count neighbors
    for (int i = 0; i < connectionsSize; i++) {
        graphSizes[connections[i][0]]++;
        graphSizes[connections[i][1]]++;
    }
    
    // Allocate memory for each adjacency list
    for (int i = 0; i < n; i++) {
        graph[i] = (int*)malloc(graphSizes[i] * sizeof(int));
        graphSizes[i] = 0; // Reset for second pass
    }
    
    // Second pass: fill adjacency lists
    for (int i = 0; i < connectionsSize; i++) {
        int a = connections[i][0], b = connections[i][1];
        graph[a][graphSizes[a]++] = b;
        graph[b][graphSizes[b]++] = a;
    }
    
    // Count connected components using DFS
    bool* visited = (bool*)calloc(n, sizeof(bool));
    int components = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(graph, graphSizes, visited, i);
            components++;
        }
    }
    
    // Clean up memory
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSizes);
    free(visited);
    
    // Need components - 1 operations to connect all
    return components - 1;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Parse connections array
    int connections[1000][2];
    int connectionsSize = 0;
    
    if (strcmp(line, "[]") != 0) {
        char* ptr = line + 1; // Skip first '['
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                connections[connectionsSize][0] = strtol(ptr, &ptr, 10);
                ptr++; // Skip comma
                connections[connectionsSize][1] = strtol(ptr, &ptr, 10);
                connectionsSize++;
                while (*ptr && *ptr != ']') ptr++; // Skip to closing bracket
                if (*ptr) ptr++; // Skip closing bracket
                if (*ptr == ',') ptr++; // Skip comma between pairs
            } else {
                ptr++;
            }
        }
    }
    
    // Convert to pointer format
    int** connectionsPtr = (int**)malloc(connectionsSize * sizeof(int*));
    for (int i = 0; i < connectionsSize; i++) {
        connectionsPtr[i] = connections[i];
    }
    
    int result = solution(n, connectionsPtr, connectionsSize);
    printf("%d\n", result);
    
    free(connectionsPtr);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Visit each computer once and each connection once during DFS traversal

✓ Linear Growth

Space Complexity

O(n + m)

Adjacency list stores n computers and m connections, plus recursion stack

⚡ Linearithmic Space

87.2K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS Component Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler