30 · Advanced Graphs: Euler Paths, Bridges & SCCs

#1192 Critical Connections in a Network

frequently reported atAmazon Google Meta

the problem

In plain words

There are n servers, numbered 0 to n − 1, joined by two-way cables connections[i] = [a, b], and every server can reach every other one. A cable is critical if removing it leaves at least one pair of servers unable to reach each other. Return all critical cables, in any order.

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

out [[1,3]]

0, 1 and 2 form a loop, so none of those cables matters alone. Cable 1–3 is the only way to reach 3. [[3,1]] is accepted too.

in n = 2, connections = [[0,1]]

out [[0,1]]

2 ≤ n ≤ 10⁵
n − 1 ≤ connections.length ≤ 10⁵
a ≠ b, and no cable is listed twice
The network is connected

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBridges & articulation points (Tarjan)Graph DFS / BFS traversal

where this runsBridges are exactly the links with no backup path — the first places to add redundancy in a computer network.

A critical cable is a bridge. One DFS finds them all: stamp each server with its arrival time tin, and compute low = the earliest arrival time its subtree can climb back to through one back edge. Tree edge u–v is a bridge exactly when low[v] > tin[u].

solutions

From brute force to optimal

For every cable, rebuild the graph without it and BFS from server 0. If some server is unreached, the cable is critical.

For each cable i: build the adjacency list without cable i.
BFS from 0 and count reached servers.
If fewer than n are reached, add cable i.

timeO(E · (V + E))

E rounds, each building the graph and running one BFS in O(V + E).

spaceO(V + E)

One adjacency list and one visited array at a time.

javajava.util.*

1class Solution {2    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {3        List<List<Integer>> critical = new ArrayList<>();4        for (int skip = 0; skip < connections.size(); skip++) {5            if (!connectedWithout(n, connections, skip)) critical.add(connections.get(skip));6        }7        return critical;8    }9 10    /** BFS from server 0 that ignores connection #skip. True if it still reaches every server. */11    private boolean connectedWithout(int n, List<List<Integer>> connections, int skip) {12        List<List<Integer>> adj = new ArrayList<>();13        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());14        for (int i = 0; i < connections.size(); i++) {15            if (i == skip) continue;16            int a = connections.get(i).get(0), b = connections.get(i).get(1);17            adj.get(a).add(b);18            adj.get(b).add(a);19        }20        boolean[] seen = new boolean[n];21        Deque<Integer> queue = new ArrayDeque<>(List.of(0));22        seen[0] = true;23        int reached = 1;24        while (!queue.isEmpty()) {25            for (int v : adj.get(queue.poll())) {26                if (seen[v]) continue;27                seen[v] = true;28                reached++;29                queue.offer(v);30            }31        }32        return reached == n;33    }34}

DFS from 0. On entering u: tin[u] = low[u] = timer++. A visited neighbour (not the parent) is a back edge: low[u] = min(low[u], tin[v]). After a child v returns: low[u] = min(low[u], low[v]), and if low[v] > tin[u], u–v is a bridge.

Build the adjacency list in both directions; fill tin with -1.
dfs(u, parent): set tin[u] = low[u] = timer++.
For each neighbour v ≠ parent: visited → low[u] = min(low[u], tin[v]); new → dfs(v, u), then low[u] = min(low[u], low[v]).
If low[v] > tin[u], add [u, v].

timeO(V + E)

Each server is entered once and each cable is looked at twice (once from each end).

spaceO(V + E)

The adjacency list holds 2E entries; tin, low and the recursion (up to V deep) add O(V).

javajava.util.*

1class Solution {2    private List<List<Integer>> adj;3    private int[] tin, low; // discovery time · lowest time the subtree can reach with one back edge4    private int timer;5    private List<List<Integer>> bridges;6 7    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {8        adj = new ArrayList<>();9        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10        for (List<Integer> c : connections) {11            adj.get(c.get(0)).add(c.get(1));12            adj.get(c.get(1)).add(c.get(0));13        }14        tin = new int[n];15        low = new int[n];16        Arrays.fill(tin, -1); // -1 = not visited yet17        timer = 0;18        bridges = new ArrayList<>();19        dfs(0, -1); // the network is connected, so one DFS reaches every server20        return bridges;21    }22 23    private void dfs(int u, int parent) {24        tin[u] = low[u] = timer++;25        for (int v : adj.get(u)) {26            if (v == parent) continue; // the edge we came in on doesn't count27            if (tin[v] != -1) {28                low[u] = Math.min(low[u], tin[v]); // back edge: a second way up29            } else {30                dfs(v, u); // tree edge: explore v's side first31                low[u] = Math.min(low[u], low[v]);32                if (low[v] > tin[u]) bridges.add(List.of(u, v)); // v's side can't reach u or above33            }34        }35    }36}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    private List<List<Integer>> adj;3    private int[] tin, low; // discovery time · lowest time the subtree can reach with one back edge4    private int timer;5    private List<List<Integer>> bridges;6 7    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {8        adj = new ArrayList<>();9        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10        for (List<Integer> c : connections) {11            adj.get(c.get(0)).add(c.get(1));12            adj.get(c.get(1)).add(c.get(0));13        }14        tin = new int[n];15        low = new int[n];16        Arrays.fill(tin, -1); // -1 = not visited yet17        timer = 0;18        bridges = new ArrayList<>();19        dfs(0, -1); // the network is connected, so one DFS reaches every server20        return bridges;21    }22 23    private void dfs(int u, int parent) {24        tin[u] = low[u] = timer++;25        for (int v : adj.get(u)) {26            if (v == parent) continue; // the edge we came in on doesn't count27            if (tin[v] != -1) {28                low[u] = Math.min(low[u], tin[v]); // back edge: a second way up29            } else {30                dfs(v, u); // tree edge: explore v's side first31                low[u] = Math.min(low[u], low[v]);32                if (low[v] > tin[u]) bridges.add(List.of(u, v)); // v's side can't reach u or above33            }34        }35    }36}

Replace recursion with an ArrayDeque and next[u], the index of u's next neighbour. Popping u is the "return": update its parent's low and run the bridge test there.

Push 0 with tin/low set. While the stack isn't empty, peek u.
If u has a neighbour left: skip the parent; visited → back edge; new → set tin/low, parent, push.
Else pop u: low[p] = min(low[p], low[u]); if low[u] > tin[p], add [p, u].

timeO(V + E)

Exactly the same work as the recursive version.

spaceO(V + E)

The stack lives on the heap, so a 10⁵-server chain can't overflow the call stack.

javajava.util.*

1class Solution {2    /** The same low-link DFS with an explicit stack: no StackOverflowError on a 10⁵-server chain. */3    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {4        List<List<Integer>> adj = new ArrayList<>();5        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());6        for (List<Integer> c : connections) {7            adj.get(c.get(0)).add(c.get(1));8            adj.get(c.get(1)).add(c.get(0));9        }10        int[] tin = new int[n], low = new int[n], parent = new int[n];11        int[] next = new int[n]; // next[u] = index of u's next neighbour to look at12        Arrays.fill(tin, -1);13        List<List<Integer>> bridges = new ArrayList<>();14        Deque<Integer> stack = new ArrayDeque<>(List.of(0));15        int timer = 0;16        tin[0] = low[0] = timer++;17        parent[0] = -1;18        while (!stack.isEmpty()) {19            int u = stack.peek();20            if (next[u] < adj.get(u).size()) {21                int v = adj.get(u).get(next[u]++);22                if (v == parent[u]) continue;23                if (tin[v] != -1) {24                    low[u] = Math.min(low[u], tin[v]); // back edge25                } else {26                    tin[v] = low[v] = timer++; // tree edge: "call" v27                    parent[v] = u;28                    stack.push(v);29                }30            } else {31                stack.pop(); // u is finished: "return" to its parent32                int p = parent[u];33                if (p == -1) continue;34                low[p] = Math.min(low[p], low[u]);35                if (low[u] > tin[p]) bridges.add(List.of(p, u));36            }37        }38        return bridges;39    }40}

in the room

How to say it in the interview

talk track

Restate: "Critical connections are bridges — edges not on any cycle."
Offer the brute force (remove each edge + BFS, O(E·(V+E))) and say it's too slow for 10⁵.
Explain tin and low, then the test low[v] > tin[u]. Mention skipping the parent edge.
Complexity O(V + E). Flag Java recursion depth at 10⁵ and mention the iterative version.

traps

Not skipping the parent: every edge looks covered by a "back edge" and nothing is reported.
Using low[v] >= tin[u] (the articulation-point test) — it reports cables that lie on a cycle.
Updating low with low[v] before the child's DFS has finished.
Recursion 10⁵ deep in Java on a long chain → StackOverflowError.

what they ask next

Follow-ups

Which servers (not cables) are single points of failure?

Articulation points: the same DFS, but a non-root u is a cut vertex if some child has low[v] ≥ tin[u], and the root is one if it has 2+ DFS children.

What if two cables can join the same pair of servers?

Skip the parent EDGE (pass the edge id down), not the parent vertex — the second cable is a real alternative path.

Minimum Number of Days to Disconnect Island (LC 1568)?

The answer is always 0, 1 or 2: 0 if it's already split, 1 if some land cell is an articulation point (or a single cell), else 2.

before you submit

Edge cases to test

A single loop through every server → no critical cable.
A tree (n − 1 cables) → every cable is critical.
Two loops sharing one server (a figure eight) → no critical cable, though that server is a cut vertex.
A 10⁵-server chain → recursion depth 10⁵ in a recursive DFS.

practise next