Critical Connections in a Network — Tarjan's Bridge Algorithm [LC 1192, Google, Amazon, Meta]

Problem Statement#

A server network is modelled as an undirected graph with n servers numbered 0..n-1 and connections[i] = [a, b] representing a bidirectional link. A critical connection (a.k.a. bridge) is an edge whose removal disconnects the graph. Return all critical connections in any order.

Constraints:

• 2 <= n <= 10^5
• n - 1 <= connections.length <= 10^5
• The graph is connected and has no duplicate edges.

Example 1:

Input:  n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: Removing 1-3 disconnects vertex 3. The triangle 0-1-2-0 has
no critical edges because each edge is part of a cycle.

Example 2:

Input:  n = 6, connections = [[0,1],[1,2],[2,0],[1,3],[3,4],[4,5],[5,3]]
Output: [[1,3]]
Explanation: Both triangles (0,1,2) and (3,4,5) are internally redundant.
The only bridge is the connector 1-3.

Why This Problem Matters#

LeetCode 1192 is the canonical interview test for Tarjan's bridge algorithm — a single DFS with two arrays (disc and low) that finds every edge whose removal disconnects the graph in O(V + E). Google, Amazon, and Meta all ask it because it tests three skills together: implementing iterative-or-recursive DFS, reasoning about back-edges in an undirected graph, and computing low-link values without bugs.

Bridge detection is everywhere in production systems. Networking tools use it to identify single-points-of-failure links in router topologies. Distributed systems use it to plan resilient replication. Compiler IRs use it to find uninterruptible regions. Social-network systems use it to expose communities connected by a single weak tie. Whenever the question is "which edges are mission-critical?" the answer is bridges.

The interview value is that the algorithm is not obvious if you have not studied it. A naive O(E * (V + E)) "remove each edge and re-run BFS" works but TLEs on n = 10^5. Tarjan's reduction to a single DFS is the elegant trick that interviewers want to see — and once you know it, you also know how to find articulation points, strongly connected components (Tarjan SCC and Kosaraju), and biconnected components, because they all share the discovery-time / low-link skeleton.

The Core Insight#

Run a DFS from any node. For each visited vertex u, record:

• disc[u] — the discovery time, i.e. the DFS entry order.
• low[u] — the smallest discovery time reachable from the subtree rooted at u, including u itself, using at most one back-edge.

low[u] is computed during the DFS post-order:

low[u] = min(
  disc[u],
  low[v] for every tree-child v,
  disc[w] for every back-edge u-w (w != parent(u))
)

Bridge condition: edge (u, v) where v is a tree-child of u is a bridge iff low[v] > disc[u]. Intuition: if the subtree rooted at v cannot reach any ancestor of u (including u) via a back-edge, then removing u-v disconnects v's subtree.

For undirected graphs, you must skip the immediate parent so a tree edge is not mistaken for a back-edge. A subtle gotcha: with parallel edges (two distinct edges between the same pair), the parent-skip should track edge indices, not just parent vertex — otherwise both edges of a multi-edge get incorrectly skipped.

Time O(V + E), space O(V + E) for adjacency list plus O(V) for the recursion stack.

Visual Dry Run#

connections = [[0,1], [1,2], [2,0], [1,3]]. DFS from 0; timer starts at 0.

Output: [[1, 3]].

Solution (Optimal)#

Python — Tarjan's bridge DFS#

import sys
from collections import defaultdict
sys.setrecursionlimit(2 * 10 ** 5)
 
def criticalConnections(n, connections):
    adj = defaultdict(list)
    for u, v in connections:
        adj[u].append(v)
        adj[v].append(u)
 
    disc = [-1] * n
    low = [0] * n
    bridges = []
    timer = 0
 
    def dfs(u, parent):
        nonlocal timer
        disc[u] = low[u] = timer
        timer += 1
        for v in adj[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append([u, v])
            else:
                low[u] = min(low[u], disc[v])
 
    dfs(0, -1)
    return bridges

JavaScript — iterative Tarjan to avoid stack overflow#

function criticalConnections(n, connections) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of connections) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const disc = new Array(n).fill(-1);
    const low = new Array(n).fill(0);
    const bridges = [];
    let timer = 0;
 
    // iterative DFS using an explicit stack
    const stack = [[0, -1, 0]]; // [node, parent, neighborIndex]
    disc[0] = low[0] = timer++;
    while (stack.length) {
        const frame = stack[stack.length - 1];
        const [u, parent, idx] = frame;
        if (idx < adj[u].length) {
            frame[2]++;
            const v = adj[u][idx];
            if (v === parent) continue;
            if (disc[v] === -1) {
                disc[v] = low[v] = timer++;
                stack.push([v, u, 0]);
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        } else {
            stack.pop();
            if (parent !== -1) {
                low[parent] = Math.min(low[parent], low[u]);
                if (low[u] > disc[parent]) bridges.push([parent, u]);
            }
        }
    }
    return bridges;
}

Complexity#

Common Mistakes#

• Naive remove-edge + BFS brute force. O(E * (V + E)) TLEs on n = 10^5.
• Tracking parent vertex instead of parent edge index. Breaks on parallel edges between the same pair: the second edge is an alternate route, but a vertex-level parent skip drops it.
• Using low[u] = min(low[u], low[v]) for back-edges. Back-edges should use disc[v], not low[v]. Mixing them up still happens to give the right bridges in many cases but is incorrect for articulation points.
• Recursion depth on n = 10^5. Default Python recursion limit is 1000. Either bump it or use the iterative version.
• Forgetting to skip the immediate parent edge. Without it, every tree edge is also a back-edge and you find no bridges.

Interview Tips#

• Open with: "Tarjan's bridge algorithm runs a single DFS, tracking disc[u] and low[u]. Edge (u, v) is a bridge iff low[v] > disc[u] for tree-children v."
• Distinguish bridges (edges) from articulation points (vertices). The bridge condition uses strict >; the articulation condition uses >= with extra root handling.
• Mention the parallel-edge gotcha — it shows seniority. Use edge indices instead of parent vertices for robustness.
• For n = 10^5, mention iterative DFS or raised recursion limit.
• If asked about offline performance, note that bridges can be found incrementally with link-cut trees in O((V + E) alpha)-amortised — overkill for this problem but a nice deep-dive.

Follow-up Questions#

• Find articulation points (cut vertices) instead of bridges. Same DFS; the condition is low[v] >= disc[u] for non-root u, and the root is articulation iff it has more than one DFS child.
• Find biconnected components. Push edges onto a stack during DFS; pop when an articulation point is reached. Each pop yields one BCC.
• Online bridge maintenance under edge insertions/deletions. Use Euler tour trees or link-cut trees.
• Strongly connected components on a directed graph. Same skeleton — Tarjan SCC also uses disc and low plus an explicit stack.

Key Takeaways#

• A bridge is an edge whose removal disconnects the graph; LeetCode 1192 asks for all of them.
• Tarjan's algorithm uses one DFS with disc[] and low[] to find bridges in O(V + E).
• Bridge condition: low[v] > disc[u] for every tree-child v of u.
• Distinguish back-edges from tree-edges by tracking the edge index of the parent, not just the parent vertex.
• The same low-link skeleton solves articulation points, biconnected components, and Tarjan SCC.
• Companies that ask this: Google, Amazon, Meta, Microsoft, Bloomberg, Stripe, Apple, ByteDance.