Problem 37.1 · Advanced Graph AlgorithmsHard

Critical Connections in a Network

What it teaches: Tarjan's bridge-finding with disc and low arrays.

Practise it on judges as “Critical Connections in a Network”.

In plain words

A cable is critical if cutting it splits the network. Explore with DFS and give each server a visit time. Also track "low": the earliest visit time a server can reach using its subtree plus one shortcut back. If a child can't reach back to its parent or earlier, the cable to it is critical.

Return all critical connections. Example: n = 4, [[0,1],[1,2],[2,0],[1,3]] → [[1, 3]].

The problem

Servers 0..n−1 are connected by undirected connections. Return every connection whose removal disconnects some servers, in any order.

Example 1

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

Constraints

2 ≤ n ≤ 10⁵
Connected, no repeated edges

Pattern clues in the wording

→ Single points of failure
→ Edge whose removal disconnects

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	n = 4 connections = [[0,1],[1,2],[2,0],[1,3]]	[[1,3]]
2	n = 2 connections = [[0,1]]	[[0,1]]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Tarjan bridges · O(V + E)

Tarjan bridges

Time O(V + E) Space O(V + E)

One DFS computing disc and low; skip the edge back to the parent; record bridges.

▶ Dry run: Tarjan: disc and lown = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

disc / low(map)

0: 0 / 01: 1 / 12: 2 / 2

Step 1/4DFS visits 0, then 1, then 2, stamping visit times 0, 1, 2.

Approach 1

import java.util.*;

class Solution {
    private List<List<Integer>> adj;
    private int[] disc, low;
    private int time = 0;
    private final List<List<Integer>> bridges = new ArrayList<>();

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (List<Integer> e : connections) { adj.get(e.get(0)).add(e.get(1)); adj.get(e.get(1)).add(e.get(0)); }
        disc = new int[n];
        low = new int[n];
        Arrays.fill(disc, -1);
        dfs(0, -1);
        return bridges;
    }

    private void dfs(int u, int parent) {
        disc[u] = low[u] = time++;
        for (int v : adj.get(u)) {
            if (v == parent) continue;
            if (disc[v] == -1) {
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) bridges.add(List.of(u, v));
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
}

Verdict: Linear; trying each edge removal would be O(E × (V + E)).

Before you submit

Edge cases and common mistakes

Test these inputs

A tree (every edge is a bridge)
A single cycle (no bridges)

Mistakes people make

Skipping every edge to the parent's id (wrong with parallel edges; skip the edge, not the node, if duplicates exist).

Interview

Follow-up questions

How would you make it iterative for 10⁵ nodes?

Connect the dots

Where this shows up in real systems

System Design · Topic 14.10 — Limiting Blast Radius: Cells, Shuffle Sharding & RegionsA bridge or articulation point in the dependency graph is a single point of failure.