1192 - Critical Connections in a Network

Difficulty: Hard | Pattern: Tarjan's Bridge-Finding Algorithm | Company tags: Amazon, LinkedIn

Problem Statement

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections where connections[i] = [ai, bi] represents a connection between servers ai and bi.

Any server can reach any other server directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Example:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[0,1],[1,2],[2,0]] form a cycle; removing any one still leaves connectivity.
             [1,3] is a bridge: removing it disconnects node 3.

Approach: Tarjan's Bridge Algorithm — O(V+E)

Key insight: Use DFS and track discovery time (disc) and low value (low). low[v] = minimum discovery time reachable from the subtree of v. An edge (u,v) is a bridge if low[v] > disc[u] — meaning v's subtree cannot reach back to u or above.

def criticalConnections(n: int, connections: list[list[int]]) -> list[list[int]]:
    graph = [[] for _ in range(n)]
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    
    disc = [-1] * n
    low = [0] * n
    timer = [0]
    bridges = []
    
    def dfs(node, parent):
        disc[node] = low[node] = timer[0]
        timer[0] += 1
        
        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            if disc[neighbor] == -1:  # unvisited
                dfs(neighbor, node)
                low[node] = min(low[node], low[neighbor])
                if low[neighbor] > disc[node]:
                    bridges.append([node, neighbor])
            else:
                low[node] = min(low[node], disc[neighbor])
    
    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)
    
    return bridges

Key Concepts

• Discovery time (disc[v]): When node v was first visited in DFS
• Low value (low[v]): Lowest discovery time reachable from v's subtree (via back edges)
• Bridge condition: low[v] > disc[u] means v's subtree can't reach u's ancestor → edge (u,v) is a bridge

Example Trace

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

DFS from 0: disc=[0,1,2,3], low=[0,0,0,3]

For edge (1,3): low[3]=3 > disc[1]=1 → bridge ✓ For edge (0,1): low[1]=0 not > disc[0]=0 → not a bridge For edge (1,2): low[2]=0 not > disc[1]=1 → not a bridge (2→0 back edge keeps it connected)

Edge Cases

• All edges form one cycle → no bridges
• Tree (no cycles) → every edge is a bridge
• Multiple components → run DFS for each unvisited node

Complexity

• Time: O(V + E)
• Space: O(V + E) for adjacency list + arrays

Note: Tarjan's is a well-known competitive programming algorithm — worth knowing the pattern well for interviews at top tech companies.