Critical Connections in a Network: A Step-by-Step Interview Walkthrough

Critical Connections in a Network is a genuinely hard graph problem, the kind where knowing the right algorithm matters more than coding speed. It asks you to find every bridge in a graph — an edge whose removal would split the network into disconnected pieces. The brute-force approach (remove each edge, check if the graph falls apart) is easy to describe but far too slow, and there's no gentle middle ground; the efficient solution requires a genuinely clever idea known as Tarjan's bridge-finding algorithm. Interviewers use this problem to see two things: whether you understand what makes an edge structurally critical (it's the only thing holding two parts of the graph together — there's no alternate path around it), and whether you can work with the discovery-time and low-link machinery that detects this in a single DFS pass. It's a problem that rewards understanding the theory, not just pattern-matching.

Finding bridges is a real, high-stakes operation in network reliability. Telecom and data-center engineers identify single points of failure — links whose loss would partition the network — so they can add redundancy. Power-grid operators find transmission lines whose failure would island part of the grid. Transportation planners find roads or bridges (literally) whose closure would cut off a region. Distributed-systems designers identify connections whose loss would split a cluster. Anywhere robustness matters, finding the edges that aren't backed up by an alternate path is exactly this problem.

Problem Statement

You are given an undirected connected graph with n nodes labeled 0 to n - 1, represented by a list of edges where connections[i] = [u, v] is an undirected edge between u and v.

A critical connection (also called a bridge) is an edge whose removal disconnects the graph.

Return all critical connections in the network.

Example: 

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

result → [[1,3]]. The edges 0–1, 1–2, 2–0 form a triangle (each is backed up by the other two), but 1–3 is the only link to node 3, so removing it isolates node 3.

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.

Input: an integer n and a list of undirected edges forming a connected graph.

Output: a list of all bridges — edges whose removal disconnects the graph.

Details to clarify:

• Is the graph guaranteed connected initially? Yes — so "disconnects the graph" is well-defined; removing a bridge creates two or more components.

• Is the graph undirected? Yes — which matters for how we handle the edge back to a node's parent during traversal.

• Does the order of returned edges matter? No — any order is fine, and the two endpoints of each edge can be in either order.

• Do we return all bridges or just one? All of them.

• Can there be duplicate edges or self-loops? Assume a clean simple graph unless told otherwise — though it's worth asking, since multi-edges change which edges are bridges.

The thing to flag is what makes an edge critical: it's critical exactly when there's no alternate path between its two endpoints. If you can get from u to v some other way, then the edge u–v is redundant — removing it doesn't disconnect anything. If the edge u–v is the only route between those parts of the graph, it's a bridge. That "is there an alternate path?" framing is the heart of the problem, and the entire efficient algorithm is a clever way to answer it for every edge at once.

2. Identify the Category of the Question

A few signals jump out:

• We have an undirected graph and need to analyze its structure.

• The property we're after — "removing this edge disconnects the graph" — is about redundancy: is this edge backed up by an alternate route?

• We need to find all such edges efficiently.

That combination — undirected graph, find all bridges, do it efficiently — points to Tarjan's bridge-finding algorithm, a single-pass DFS that uses discovery times and low-link values to detect bridges. Same family as Tarjan's algorithm for articulation points and strongly connected components — all of them exploit the structure of the DFS tree and the timestamps of when nodes are first visited. If you hear "bridge" or "critical edge," this machinery should come to mind.

3. Brute Force Solution

Let's think about the naive approach to understand the problem. The definition of a bridge is operational: an edge whose removal disconnects the graph. So the most direct algorithm just does that — for each edge, remove it, then check whether the graph is still connected.

for each edge (u, v):
    remove (u, v)
    run DFS/BFS from any node
    if not all nodes reachable:
        (u, v) is a bridge
    restore (u, v)

Each connectivity check is a full traversal, O(n + e). We do one per edge, so the total is O(e × (n + e)) — far too slow for large graphs.

The brute force is genuinely useful here, though, because it pins down what "critical" means: an edge is a bridge precisely when removing it leaves some nodes unreachable — that is, when there's no other path connecting the two sides. So the real question for each edge u–v is: is there an alternate route from u to v that doesn't use this edge? The efficient algorithm is essentially a way to answer that "alternate route?" question for every edge in a single traversal instead of one traversal per edge.

4. Brainstorm More Solutions

Step 1: A DFS sorts every edge into one of two kinds

So far we've been thinking about bridges one edge at a time — "is this edge backed up by an alternate path?" — but checking each edge in isolation is what made the brute force slow. We need a way to learn about every edge from a single sweep of the graph. DFS is a natural candidate, because it doesn't just visit nodes — it imposes a structure on them. As it explores, it builds a tree of "who discovered whom," and that tree quietly records, for every edge, how the two endpoints relate: whether one discovered the other, or whether they were already connected by some earlier route. That second kind of relationship is precisely the "alternate path" signal we're hunting for. So instead of asking about edges one by one, let's run a single DFS and study the structure it leaves behind.

As DFS explores, it travels along some edges to reach brand-new nodes — those edges form a tree, the DFS tree, with the starting node at the root. We'll call these tree edges.

But not every edge gets used for discovery. Sometimes, from the node we're currently exploring, an edge leads to a node we've already visited — one that's an ancestor of ours, sitting somewhere above us on the current path back to the root. We can call these back edges. (In an undirected graph, these are the only two possibilities — every edge is either a tree edge or a back edge.)

A back edge connects a node down here to an ancestor up there. If we follow the tree path from the ancestor down to our node, then take the back edge back up, you've traced a loop — a cycle. So back edges are exactly the things that create cycles in our graph.

And what happens if we remove an edge that's part of a loop? The rest of the loop is still intact and can act as a detour, and the two endpoints are still connected the long way around. In other words, the cycle is the alternate path. So our hunt for bridges is really a hunt for edges that aren't protected by any cycle, because an edge on a cycle can never be a bridge.

Step 2: When does a tree edge have no cycle protecting it?

Can we pin down this rule about cycles into something more concrete? Let's try zooming in on a single tree edge, from parent u down to child v.

Below v hangs v's entire subtree — all the nodes DFS discovered by going through v.

Now imagine cutting the edge u–v. Everything in v's subtree is suddenly dangling, connected to the rest of the graph only through... what? The only way the subtree stays attached is if some node inside it has a back edge that climbs up to u or even higher — to one of u's ancestors. That back edge would be a second route in and out of the subtree, a detour around the cut.

So the rule is clean: u–v is a bridge exactly when nothing in v's subtree can reach u or any of u's ancestors, except by using the edge u–v itself. One back edge climbing high enough, and the subtree has a backup route — which means the edge is not a bridge. No such back edge anywhere in the subtree, and u–v is the subtree's only lifeline — a.k.a a bridge.

This turns our vague question into a concrete one: for the subtree hanging under v, how high up the tree can it reach through back edges? If it can reach u or above, u–v is safe. If the best it can do is stay below u, then u–v is a bridge. We just need a way to measure "how high can this subtree reach."

Step 3: Two numbers that let us measure "how high can it reach"

To measure reach, we need a notion of "higher" and "lower" in the tree. DFS gives us one for free: just stamp each node with the order it was discovered.

So define, for each node u:

• disc[u] — its discovery time. The root is discovered at time 0, the next node at time 1, and so on. A node discovered earlier (smaller number) is higher up the tree, closer to the root. This stamp never changes once set.

Now we want, for each node, a measure of the highest ancestor its subtree can climb back to. That's the second number:

• low[u] — its low-link value. The smallest discovery time that u can reach using any path that goes down through its subtree and then takes one back edge up. In plain terms: "what's the earliest disc[u] (discovery time) that u, or anything beneath u, can climb back to?"

• If u's subtree contains a back edge to some node k discovered way back near the root, node k's tiny discovery smaller becomes reachable, so low[u] drops to that smaller disc[k] number.

• If the subtree has no back edges escaping upward at all, there's nothing to pull low[u] below u's own discovery time, so low[u] just equals disc[u] — the subtree is trapped at its own level.

To formalize that logic as a test: for a tree edge from parent u to child v, if low[v] <= disc[u], then v's subtree can reach u or higher through some back edge. That back edge is the alternate route, so u–v is safe.

Or equivalently: for a tree edge from parent u to child v, u–v is a bridge if and only if low[v] > disc[u]. Even the highest v's subtree can reach is still lower (has a later discovery time) than u. No back edge rescues it — so the edge u–v is its only connection, and cutting it strands the subtree, making it a bridge.

Step 4: Computing both numbers in one DFS pass

So now that we know what numbers we're tracking, disc and low, let's think about how we fill them out.

When DFS arrives at a node u, first we stamp it: set both disc[u] and low[u] to the current clock value, then tick the clock forward. (We start low[u] equal to disc[u] because, before exploring, the highest u knows it can reach is itself.)

Then we look at each neighbor v, and see that there are 3 cases we need to think through:

• v is the parent we came from — skip it. The edge back to our parent isn't an alternate route; it's the tree edge we just walked down. Counting it would fool us into thinking every node has a "way back up," and we'd never find any bridges. (This is the one subtlety unique to undirected graphs.)

• v is unvisited — this is a tree edge, so recurse into v. When that recursive call returns, v's subtree has been fully explored and low[v] holds its best reach. We absorb it: low[u] = min(low[u], low[v]), because anything v's subtree can reach, u can reach too by going through v. Right here, with low[v] freshly computed, we apply the bridge test: if low[v] > disc[u], record u–v as a bridge.

• v is already visited and isn't the parent — this is a back edge straight to an ancestor. We can climb to v's level, so low[u] = min(low[u], disc[v]).

The min operations are the engine: a back edge pulls a node's low value down toward an earlier ancestor, and as each recursive call returns, the child hands its low up to the parent. Reach information bubbles upward through the tree until every node knows the highest its own subtree can climb — which is exactly what the bridge test needs.

Step 5: Walk through the example

Let's trace n = 4, edges [[0,1],[1,2],[2,0],[1,3]]. Adjacency: 0↔1, 1↔2, 2↔0, 1↔3.

DFS from 0 (parent -1):

• Visit 0: disc[0] = low[0] = 0. Neighbors: 1, 2.

  • Visit 1 (parent 0): disc[1] = low[1] = 1. Neighbors: 0 (parent, skip), 2, 3.

    • Visit 2 (parent 1): disc[2] = low[2] = 2. Neighbors: 1 (parent, skip), 0.

      • 0 is visited and not the parent → back edge. low[2] = min(2, disc[0]=0) = 0.

    • Return from 2. low[1] = min(1, low[2]=0) = 0. Bridge check for edge 1–2: low[2]=0 > disc[1]=1? No. Not a bridge.

    • Visit 3 (parent 1): disc[3] = low[3] = 3. Neighbors: 1 (parent, skip). No other neighbors.

    • Return from 3. low[1] = min(0, low[3]=3) = 0. Bridge check for edge 1–3: low[3]=3 > disc[1]=1? Yes. Bridge! Record [1, 3].

  • Return from 1. low[0] = min(0, low[1]=0) = 0. Bridge check for edge 0–1: low[1]=0 > disc[0]=0? No. Not a bridge.

  • Neighbor 2 of node 0 is already visited (and not... wait, 0's parent is -1) → back edge. low[0] = min(0, disc[2]=2) = 0. No change.

Result: [[1, 3]]. Correct — the triangle 0–1–2 is fully redundant (every edge sits on the cycle), and 1–3 is the lone bridge to node 3.

Step 6: Complexity

The algorithm is a single DFS. Each node is visited once, and across the whole traversal each edge is examined a constant number of times (once from each endpoint). So the time is O(n + e) — linear in the size of the graph.

Space is O(n) for the disc and low arrays and O(n + e) for the adjacency list, plus O(n) for the recursion stack in the worst case (a deep tree). So O(n + e) overall.

This is a dramatic improvement over the brute force's O(e × (n + e)). The whole point of the discovery-time/low-link machinery is to answer "does an alternate path exist?" for every edge in one pass, instead of re-running connectivity checks edge by edge.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Remove each edge, recheck connectivity	O(e × (n + e))	O(n)	Never for large graphs — but it defines what a bridge is
Tarjan's bridge-finding (DFS + low-link)	O(n + e)	O(n + e)	The standard answer — finds all bridges in one pass

This is one of those problems where there isn't a spectrum of intermediate solutions — you either know the low-link technique or you're stuck with the slow brute force. Recognizing "bridge" → "Tarjan's algorithm" and being able to reason through the low[v] > disc[u] condition is what the problem is testing.

6. Pseudocode

build undirected adjacency list
disc[] = -1 for all nodes      # -1 means unvisited
low[]  = 0 for all nodes
time = 0
result = []

dfs(u, parent):
    disc[u] = low[u] = time
    time++
    for each neighbor v of u:
        if v == parent:
            continue  # don't treat the parent edge as a back edge
        if disc[v] == -1: # tree edge — v unvisited
            dfs(v, u)
            low[u] = min(low[u], low[v])  # inherit child's reach
            if low[v] > disc[u]:   # subtree can't reach u or above
                result.add([u, v]) # → bridge
        else:                      # back edge — v already visited
            low[u] = min(low[u], disc[v])

dfs(0, -1)
return result

7. Edge Cases

Things to verify before claiming we're done:

• A linear chain (0–1–2–3) → no cycles anywhere, so every edge is a bridge. The low-link condition holds at each tree edge. ✓

• A single cycle (triangle) → every edge sits on the cycle, so no edge is a bridge. Each child's subtree reaches back up via the cycle. ✓

• A graph with both cyclic and tree-like parts (the example) → only the tree-like edges that aren't backed by a cycle are bridges. ✓

• Deep recursion (long chain) → the DFS recursion depth can reach n; for very large graphs an iterative DFS may be needed to avoid stack overflow. Worth mentioning.

• A single edge connecting two nodes → that edge is trivially a bridge.

Disconnected input isn't a concern here — the problem guarantees the graph starts connected. The parent-skip check is the subtle correctness detail: in an undirected graph, the edge back to your parent must not be mistaken for an alternate route, or you'd never detect any bridges.

8. Write Full Code

import java.util.*;

public class CriticalConnections {

    private static int time = 0;

    public static List<List<Integer>> criticalConnections(
            int n,
            List<List<Integer>> connections
    ) {
        // Build undirected adjacency list
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (List<Integer> edge : connections) {
            int u = edge.get(0), v = edge.get(1);
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        // discovery time; -1 = unvisited
        int[] disc = new int[n]; 
        Arrays.fill(disc, -1);

        // earliest reachable discovery time from subtree
        int[] low = new int[n];  

        List<List<Integer>> result = new ArrayList<>();
        time = 0;
        dfs(0, -1, graph, disc, low, result);
        return result;
    }

    private static void dfs(
            int u, int parent,
            List<List<Integer>> graph,
            int[] disc, int[] low,
            List<List<Integer>> result
    ) {
        disc[u] = low[u] = time++;

        for (int v : graph.get(u)) {
            if (v == parent) {
                // Skip the edge we arrived on — it's not an 
                // alternate route
                continue;
            }
            if (disc[v] == -1) {
                // Tree edge: recurse, 
                // then absorb the child's reach
                dfs(v, u, graph, disc, low, result);
                low[u] = Math.min(low[u], low[v]);

                // If v's subtree can't climb to u or above, 
                // u-v is a bridge
                if (low[v] > disc[u]) {
                    result.add(List.of(u, v));
                }
            } else {
                // Back edge: u can reach as high as v's 
                // discovery time
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
}

9. Test the Code

// The canonical example: triangle + a pendant edge
List<List<Integer>> e1 = List.of(
    List.of(0, 1), List.of(1, 2), List.of(2, 0), List.of(1, 3)
);
System.out.println(criticalConnections(4, e1));
// [[1, 3]]

// Linear chain — every edge is a bridge
List<List<Integer>> e2 = List.of(
    List.of(0, 1), List.of(1, 2), List.of(2, 3)
);
System.out.println(criticalConnections(4, e2));
// [[0,1],[1,2],[2,3]] (order may vary)

// Single cycle — no bridges
List<List<Integer>> e3 = List.of(
    List.of(0, 1), List.of(1, 2), List.of(2, 0)
);
System.out.println(criticalConnections(3, e3));
// [] (empty — the cycle backs up every edge)

// Two cycles joined by a single bridge edge
List<List<Integer>> e4 = List.of(
    List.of(0, 1), List.of(1, 2), List.of(2, 0),   // cycle A
    List.of(3, 4), List.of(4, 5), List.of(5, 3),   // cycle B
    List.of(2, 3)                                   // the only link between them
);
System.out.println(criticalConnections(6, e4));
// [[2, 3]]

These hit the meaningful cases: the canonical triangle-plus-pendant, a linear chain (all edges critical), a pure cycle (no edges critical), and two cycles joined by a single edge (only the joining edge is critical). The last case is the clearest illustration of the core idea — each cycle internally backs up its own edges, so only the lone connector between them is a bridge.

10. Key Lessons

• An edge is a bridge exactly when there's no alternate path between its endpoints. Every efficient bridge algorithm is fundamentally a way to answer "does an alternate route exist?" for every edge — and in DFS terms, alternate routes are back edges that create cycles.

• Classify edges by the DFS tree. In an undirected graph, every edge is either a tree edge (discovers a new node) or a back edge (connects to an ancestor). Back edges are the cycles, and edges on cycles are never bridges. This classification is the foundation of Tarjan's family of algorithms.

• The low-link value low[u] captures "the highest ancestor u's subtree can reach." Comparing it to a parent's discovery time (low[v] > disc[u]) is the precise test for whether a subtree is stranded without its connecting edge. Understanding what low means is more important than memorizing the comparison.

• In undirected-graph DFS, skip the edge back to your parent. Treating it as a back edge would falsely suggest an alternate route and break bridge detection. This parent-skip is the classic correctness subtlety.

• Some problems reward theory over improvisation. There's no clever intermediate solution between brute force and Tarjan's here — recognizing the named technique and understanding its invariants is the path. When you see "bridge," "articulation point," or "strongly connected component," reach for discovery times and low-link values.

The thing that makes Critical Connections click is the discovery-time and low-link machinery that lets a single traversal answer "is this edge backed up by an alternate path?" for every edge at once. Once you understand that low[v] measures how high a subtree can climb, and that an edge is a bridge precisely when its child's subtree can't climb past the parent, the cryptic-looking low[v] > disc[u] condition becomes a direct statement of "this subtree has no other way out." That understanding is the rite of passage that opens up the whole family of Tarjan's algorithms — articulation points and strongly connected components all run on the same idea.

Good Luck and Happy Coding!