Critical Connections in a Network

Problem in Plain English

Find every undirected network connection whose removal disconnects some servers. Discovery times and low links identify these bridges in one traversal.

Problem Statement

A connected undirected network has n servers numbered from 0 to n - 1 and edges connections, where [a, b] joins two distinct servers. There are no repeated connections.

Return all connections whose removal makes some servers unable to reach others. These edges are called bridges. Edge orientation and answer order do not matter.

Constraints

2 <= n <= 10^5
n - 1 <= connections.length <= 10^5
Endpoints are distinct and in [0, n - 1]; there are no repeated connections.
The network is connected.

Examples

Example 1

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

The triangle has an alternate route around each of its edges. Server 3 is attached only through 1, so removing 1-3 isolates it.

Example 2

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

The single connection is the only route between the two servers, so it is a bridge.

Example 3

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

Removing any one edge leaves the other two as a path connecting all three servers. Equality of a child low link with an ancestor discovery time must not create a bridge.

Intuition

Removing a DFS tree edge disconnects its child subtree only if that subtree has no alternate route back to the parent or an earlier ancestor. In Example 1, 2 can reach 0 without using its parent edge, protecting the triangle 0-1-2. Server 3 has no such escape, so 1-3 is a bridge. A low link summarizes the earliest discovery reachable by going down tree edges and then taking one non-parent edge.

Approaches

Tarjan Bridges

Optimal

Solution Details

Reveal Tarjan Bridges: intuition, complexity, and code

Intuition

Find bridges by measuring each DFS subtree’s earliest escape. Testing connectivity after removing every edge costs O(m(n + m)); low links summarize all those alternate-route checks in one linear traversal. Explicit frames handle a 100,000-server chain without recursion.

Step-by-Step Logic

Give each input edge an ID and store both adjacency directions with that same ID. Initialize discovery times to -1.
Discover 0 at time 0, then 1 at 1 and 2 at 2. Skip only the exact edge used to enter a node.
At 2, edge 2-0 is not its parent edge. Lower low[2] from 2 to disc[0] = 0. On returning to 1, propagate this value to low[1].
Discover 3 at time 3 from 1. Its only edge is the parent edge, so it finishes with low[3] = 3.
Since 3 > disc[1] = 1, record [1,3]. Finish 1 with low[1] = 0, which is not greater than disc[0] = 0.
Return [[1,3]]. Perform the comparison only after a child finishes, when its low link includes every descendant.

Why It Works

DFS discovery numbers order ancestors before descendants. After a child subtree finishes, low[child] is the smallest discovery number reachable inside that subtree or through a non-parent edge from it. If low[child] is at most disc[parent], an alternate connection reaches the parent or one of its ancestors, so removing the tree edge leaves the subtree connected. If low[child] is greater, no such connection exists. In an undirected DFS, edges outside the tree connect ancestors and descendants; there is no undiscovered cross-subtree escape to overlook. The tree edge is therefore a bridge exactly under the strict greater-than test. Non-tree edges already lie on a tree-path cycle and cannot be bridges. Edge IDs ensure the traversal ignores only the incoming edge, even if reused outside the stated no-parallel-edge contract.

Dry Run

Tarjan Bridges: variable states at each step
Event	disc	low change	Bridge decision
Enter 0,1,2	0,1,2 respectively	low = disc initially	pending
Edge 2 to 0	disc[0]=0	low[2]: 2 to 0	skip only incoming 1-2
Finish 2	disc[1]=1	low[1]: 1 to 0	0 > 1 false; 1-2 protected
Enter and finish 3	disc[3]=3	low[3]=3	3 > 1 true; add [1,3]
Finish 1	disc[0]=0	low[0]=0	0 > 0 false; 0-1 protected
Finish 0	low[0]=0	traversal complete	return [[1,3]]

Complexity Analysis

Time Complexity

O(n + m)

Space Complexity

O(n + m)

For n servers and m connections, adjacency construction stores two entries per edge. Each entry is examined once and each vertex frame finishes once. Discovery, low, parent and cursor arrays and the frame stack use O(n); adjacency and the bridge result use O(m). No recursion or output sort is needed.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {5        List<List<int[]>> adj = new ArrayList<>();6        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());7        for (int id = 0; id < connections.size(); id++) {8            int u = connections.get(id).get(0), v = connections.get(id).get(1);9            adj.get(u).add(new int[]{v, id}); adj.get(v).add(new int[]{u, id});10        }11        int[] disc = new int[n], low = new int[n], next = new int[n];12        int[] parent = new int[n], parentEdge = new int[n];13        Arrays.fill(disc, -1); Arrays.fill(parent, -1); Arrays.fill(parentEdge, -1);14        int clock = 0;15        List<List<Integer>> answer = new ArrayList<>();16        Deque<Integer> frames = new ArrayDeque<>();17        for (int root = 0; root < n; root++) {18            if (disc[root] != -1) continue;19            disc[root] = low[root] = clock++; frames.push(root);20            while (!frames.isEmpty()) {21                int u = frames.peek();22                if (next[u] < adj.get(u).size()) {23                    int[] edge = adj.get(u).get(next[u]++);24                    int v = edge[0], id = edge[1];25                    if (id == parentEdge[u]) continue;26                    if (disc[v] == -1) {27                        parent[v] = u; parentEdge[v] = id;28                        disc[v] = low[v] = clock++; frames.push(v);29                    } else low[u] = Math.min(low[u], disc[v]);30                } else {31                    frames.pop();32                    int p = parent[u];33                    if (p != -1) {34                        if (low[u] > disc[p]) answer.add(Arrays.asList(p, u));35                        low[p] = Math.min(low[p], low[u]);36                    }37                }38            }39        }40        return answer;41    }42}

Hints

Hint 1

Removing an edge on a cycle cannot disconnect the network.

Hint 2

For each DFS subtree, remember the earliest ancestor it can reach without its incoming edge.

Hint 3

After a child finishes, its incoming edge is a bridge exactly when low[child] > disc[parent].

Edge Cases

Every edge of a chain is a bridge, including both end connections.
A single large cycle has no bridges; low equality is enough to protect an edge.
Two dense cyclic regions joined by one connection have that connection as their only bridge.

Common Mistakes and Interview Tips

Using >= in the bridge test falsely flags edges with an alternate route back to the parent.
Treating the reverse copy of the parent edge as a back edge suppresses real bridges.
Checking a child’s low link before its subtree finishes misses later escape edges.
Using SCC low-link rules for this undirected problem confuses two different stack invariants.

Key Takeaway

A DFS subtree needs only its earliest alternate escape to decide whether its incoming edge is essential. Low links summarize that escape information in linear time.