Critical Connections in a Network (LeetCode 1192) Solution

The problem

There are n servers, numbered 0 to n − 1, joined by undirected connections. The network starts connected. A connection is critical if removing it leaves some server unable to reach another. Return every critical connection.

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

Servers 0, 1 and 2 form a triangle, so removing any one triangle edge leaves the other two as a detour. The edge 1–3 is the only way to reach server 3.

How to think about it

Start with brute force. For each edge, remove it and run a DFS to check whether the graph is still connected. That is E searches of O(V + E) each: O(E · (V + E)). With 10⁵ edges, far too slow.

Name the concept. A critical connection is a bridge: an edge that lies on no cycle. Bridges are found in a single DFS with Tarjan’s algorithm.

The key insight: track how high each subtree can climb. Run a DFS and give each node a discovery time disc[u], the order in which it was first visited. Also compute low[u], the smallest discovery time reachable from u’s subtree using tree edges downward plus one back edge to an already-visited node. Now look at a tree edge u → v. If low[v] > disc[u], nothing in v’s subtree can reach u or anything above it except through this edge. Cut it, and the subtree is stranded. That edge is a bridge.

How low is computed. Start with low[u] = disc[u]. For a child v you visit for the first time, recurse, then take low[u] = min(low[u], low[v]). For a neighbour already visited (a back edge), take low[u] = min(low[u], disc[v]). Skip the edge straight back to the parent, or every edge would look like a cycle.

Which pattern is this? DFS with low-link values. The tell is “which single edge (or node) removal disconnects the graph”.

Approach

Build an adjacency list for the undirected graph.
Run a DFS. On entering u, set disc[u] = low[u] = timer and increment the timer.
For each neighbour v other than the parent: if unvisited, recurse, then set low[u] = min(low[u], low[v]), and record u–v as a bridge if low[v] > disc[u].
If v was already visited, it is a back edge: set low[u] = min(low[u], disc[v]).
Start a DFS from every unvisited node, then return the sorted bridges.

Solution

from collections import defaultdict
def critical_connections(n, connections):
    adj = defaultdict(list)
    for a, b in connections: adj[a].append(b); adj[b].append(a)
    disc = [-1] * n; low = [0] * n; timer = [0]; res = []
    def dfs(u, parent):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        for v in adj[u]:
            if v == parent: continue                     # don't treat the tree edge as a cycle
            if disc[v] == -1:
                dfs(v, u); low[u] = min(low[u], low[v])
                if low[v] > disc[u]: res.append(sorted([u, v]))   # v's subtree can't climb above u
            else:
                low[u] = min(low[u], disc[v])            # back edge
    for i in range(n):
        if disc[i] == -1: dfs(i, -1)
    return sorted(res)
# critical_connections(4, [[0,1],[1,2],[2,0],[1,3]]) -> [[1, 3]]

Dry run

Event	Detail	Effect
visit 0	`disc[0] = 0`
visit 1	`disc[1] = 1`
visit 2	`disc[2] = 2`
back edge 2 → 0	`low[2] = min(2, disc[0])`	`low[2] = 0`
return to 1 from 2	`low[2] = 0 > disc[1] = 1`? no	`low[1] = 0`
visit 3, return to 1	`low[3] = 3 > disc[1] = 1`? yes	bridge [1, 3]
return to 0 from 1	`low[1] = 0 > disc[0] = 0`? no	`low[0] = 0`

Final low is [0, 0, 0, 3], and the answer is [[1, 3]].

Complexity

Time: O(V + E). Each node is visited once and each edge is examined twice, once from each end.
Space: O(V + E). The adjacency list, the disc and low arrays, and the recursion stack, which can be V deep.

Edge cases and pitfalls

A tree (no cycles) makes every edge a bridge.
A single cycle has no bridges.
Skipping by parent node is fine here because there are no duplicate connections. With parallel edges you would skip by edge id instead, since a doubled edge is not a bridge.
Using low[v] instead of disc[v] on a back edge happens to work for bridges but is wrong for articulation points; stick to disc[v].
Recursion depth: a path of 10⁵ nodes exceeds Python’s default limit. Raise it with sys.setrecursionlimit or rewrite the DFS with an explicit stack.

Redundant Connection (LeetCode 684): the opposite question, finding an edge that lies on a cycle.
Number of Connected Components (LeetCode 323): what “disconnected” means, counted directly.
Graph Valid Tree (LeetCode 261): a graph where every edge is a bridge.