We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Operations to Make Network Connected

Difficulty: Medium

Problem 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 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.

Key Insights

  • The problem can be modeled as a graph where computers are nodes and connections are edges.
  • We need to find the number of disconnected components in the graph.
  • The number of operations required to connect all components is equal to the number of components minus one.
  • If the number of connections is less than n - 1, it is impossible to connect all computers.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of computers and m is the number of connections. Space Complexity: O(n), for storing the graph and visited nodes.

Solution

The problem can be solved using a graph traversal algorithm such as Depth-First Search (DFS) or Breadth-First Search (BFS) to find the connected components. We will first build an adjacency list from the connections, then perform DFS or BFS to count the number of distinct components. The minimum number of operations needed to connect all components is equal to the number of components minus one. We also need to check if we have enough connections to make all computers connected; if not, we return -1.

Code Solutions

def makeConnected(n, connections):
    if len(connections) < n - 1:
        return -1
    
    # Create an adjacency list
    graph = [[] for _ in range(n)]
    for a, b in connections:
        graph[a].append(b)
        graph[b].append(a)
    
    visited = [False] * n
    components = 0
    
    def dfs(node):
        stack = [node]
        while stack:
            curr = stack.pop()
            for neighbor in graph[curr]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    stack.append(neighbor)

    for i in range(n):
        if not visited[i]:
            components += 1
            visited[i] = True
            dfs(i)

    return components - 1
← Back to All Questions