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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Operations to Make Network Connected

Number: 1442

Difficulty: Medium

Paid? No

Companies: Amazon, Google, IBM, McKinsey, Nvidia, Paytm, Akuna Capital

Problem Description

Given n computers (numbered from 0 to n-1) and a list of ethernet cable connections between them, the task is to determine the minimum number of cable re-arrangements required to connect all computers into a single network. You can re-use cables from redundant connections, but if there are not enough cables available (i.e. if the total number of cables is less than n-1), then it is impossible to fully connect the network and the answer should be -1.

Key Insights

  • To connect n nodes, at least n-1 cables are needed.
  • The problem can be thought of in terms of connected components in an undirected graph.
  • Extra (redundant) cables present in cycles can be redistributed to connect the disconnected components.
  • Union Find (Disjoint Set Union) is a natural choice to efficiently count the number of connected components.

Space and Time Complexity

Time Complexity: O(n + m) where m is the number of connections. Space Complexity: O(n) for storing the parent array of the Union-Find structure.

Solution

We first check if the number of available connections is at least n-1; if not, return -1 because it is impossible to connect all computers. Next, we use the Union-Find (Disjoint Set) data structure to group connected computers. Every time we connect two computers that are not already in the same set, we merge their sets. After processing all connections, the number of distinct sets (connected components) indicates the number of isolated networks. To connect k components, we need k-1 operations (reconnection of cables). This approach is efficient and leverages path compression and union-by-rank techniques in the Union-Find data structure for optimal performance.

Code Solutions

# Define a class for Union Find data structure
class UnionFind:
    def __init__(self, n):
        # Initialize parent list: each node is its own parent
        self.parent = [i for i in range(n)]
    
    def find(self, x):
        # Find the root of x with path compression optimization
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Union sets containing x and y
        rootX = self.find(x)
        rootY = self.find(y)
        # If both nodes share the same root, they are already connected
        if rootX == rootY:
            return False
        self.parent[rootY] = rootX
        return True

def makeConnected(n, connections):
    # Check if there are enough cables to connect n computers
    if len(connections) < n - 1:
        return -1
    
    uf = UnionFind(n)
    # Start with n separate components
    components = n
    # Iterate over each connection and union the components
    for a, b in connections:
        if uf.union(a, b):
            components -= 1  # Components merge reduces count by one
    
    # The number of operations needed is the number of components minus one
    return components - 1

# Example usage:
#print(makeConnected(4, [[0,1],[0,2],[1,2]]))  # Expected output: 1
← Back to All Questions