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

Critical Connections in a Network

Number: 1300

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Bloomberg, Microsoft

Problem Description

Given an undirected network of n servers (numbered from 0 to n - 1) and a list of connections (each connection is a pair of servers), find all critical connections in the network. A critical connection (or bridge) is an edge that, if removed, will disconnect some part of the network, meaning some servers will no longer be able to communicate with others.

Key Insights

  • The problem is about identifying bridges in an undirected graph.
  • Use Depth-First Search (DFS) to explore the graph.
  • During DFS, track discovery times and low-link values for each node.
  • For an edge (u, v), if low[v] > disc[u] then (u, v) is a critical connection.
  • Tarjan's algorithm is well-suited for solving this problem in O(n + m) time.

Space and Time Complexity

Time Complexity: O(n + m) where n is the number of nodes and m is the number of connections. Space Complexity: O(n + m) for the graph representation and DFS recursion stack.

Solution

We solve this problem using a DFS-based approach (Tarjan's algorithm). First, we transform the list of connections into an adjacency list for efficient graph traversal. We then start a DFS from an arbitrary node (node 0, since the graph is connected) while maintaining two arrays: one for discovery times (disc) and one for low-link values (low). The discovery time is the time when the node is first visited, and the low-link value is the smallest discovery time that can be reached from that node (including via back edges). For each edge (u, v), after a DFS call on v, if low[v] > disc[u] then the edge (u, v) is a bridge because v (and its descendants) cannot reach u or any of its ancestors without this edge. This edge is then recorded as a critical connection.

Code Solutions

def criticalConnections(n, connections):
    # Build the adjacency list for the graph
    graph = [[] for _ in range(n)]
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    
    # Initialize discovery time and low arrays
    disc = [-1] * n  # Discovery times, -1 indicates unvisited
    low = [0] * n    # Low values for each node
    time = 0         # Global timer
    bridges = []     # List to store critical connections (bridges)
    
    def dfs(u, parent):
        nonlocal time
        disc[u] = low[u] = time
        time += 1
        
        # Traverse all adjacent nodes
        for v in graph[u]:
            if disc[v] == -1:  # If v is not visited
                dfs(v, u)
                low[u] = min(low[u], low[v])
                # If the smallest reachable vertex from v is after u's discovery, edge (u,v) is a bridge
                if low[v] > disc[u]:
                    bridges.append([u, v])
            elif v != parent:  # v is visited and is not the parent (back edge)
                low[u] = min(low[u], disc[v])
    
    # Start DFS from node 0
    dfs(0, -1)
    return bridges

# Example usage:
n = 4
connections = [[0,1],[1,2],[2,0],[1,3]]
print(criticalConnections(n, connections))  # Output: [[1, 3]]
← Back to All Questions