← DSA Atlas
Dedicated problem page · #1192

Critical Connections in a Network

HardShortest Path, Dijkstra and Minimum Spanning TreeBridge finding (Tarjan)DFS with discovery/low-link times
Solve on LeetCode ↗
1192
HardShortest Path, Dijkstra and Minimum Spanning TreeDFS with discovery/low-link timesBridge finding (Tarjan)

Critical Connections in a Network

A network has n servers labeled 0..n-1 connected by undirected connections forming a connected graph. A critical connection is an edge whose removal disconnects some servers (a bridge). Return all critical connections in any order.

Open official problem prompt ↗
In plain English

Identify every edge whose removal would split the previously connected network into pieces.

Picture it like this

In a road map, a bridge is a road that is the only way across a river - remove it and the two sides are cut off, whereas roads inside a loop always have an alternate route.

Example
Input
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output
[[1,3]]
Why
Edges 0-1, 1-2, 2-0 form a cycle so none is critical; removing 1-3 isolates server 3, so 1-3 is the only bridge.
Constraints
2 <= n <= 10^5n - 1 <= connections.length <= 10^50 <= ai, bi <= n - 1ai != biThere are no repeated connectionsThe graph is connected
Pattern lesson

See the pattern, then code

Bridge finding (Tarjan)
Recognition clue

Asking which single edges, if cut, break connectivity of an undirected graph is exactly the bridges problem, solved by Tarjan's low-link DFS.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. During DFS assign each node a discovery time. An edge u-v is a bridge exactly when the subtree rooted at v has no back-edge reaching u or any earlier node, i.e. low[v] > disc[u].

New words, made simpleKnow these before the algorithm
Bridge
An edge whose deletion increases the number of connected components.
Discovery time (disc)
The timestamp when DFS first visits a node.
Low-link (low)
The smallest discovery time reachable from a node using its subtree plus at most one back-edge.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Remove each edge and test

Too slow: up to 10^5 edges each triggering a full traversal.

Delete every edge in turn and run a connectivity check.

Time O(E * (V + E))Space O(V + E)
Best choiceTarjan's bridge DFS

Linear single pass, the standard optimal solution.

One DFS tracking discovery and low-link times marks an edge as a bridge when the child cannot reach back above the parent.

Time O(V + E)Space O(V + E)
The rule we keep true

Invariant

After DFS finishes a node v, low[v] equals the earliest discovery time reachable from v's subtree via tree edges and a single back-edge.

Why this is correct

Reasoning

If low[v] > disc[u], nothing in v's subtree can reach u or an ancestor except through the edge u-v, so that edge is the sole connector and its removal disconnects the subtree. If some back-edge reaches at or above u, an alternate route exists and the edge is not critical.

The algorithm in three movesSay these aloud before coding
1Build an adjacency list and arrays disc (discovery time) and low (lowest reachable time)

disc=[0,1,2,3], low=[0,0,0,3]

2Run DFS assigning increasing timestamps

edge 1-3: low[3]=3 > disc[1]=1 -> bridge

3For each tree edge u-v, recurse then set low[u] = min(low[u], low[v])

cycle 0-1-2: low stays 0, no bridges

4If low[v] > disc[u], edge u-v is a bridge; for back-edges update low[u] with disc[v]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
22
33
1 · Readstart DFS
2 · Askassign times
3 · Update statedisc[0]=low[0]=0
4 · ResultExplore neighbor 1.
Key takeaway

DFS timestamps reveal that only edge 1-3 has low[child] exceeding the parent's discovery time.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Build undirected graph

    Each connection adds both directions to the adjacency list.

  2. 2
    Lines 12-14Timestamp on entry

    disc and low both start at the current timer, which then advances.

  3. 3
    Lines 18-23Tree edge recursion

    After recursing into an unvisited child, pull up its low value and test the bridge condition low[v] > disc[u].

  4. 4
    Lines 24-25Back edge update

    For an already-visited non-parent neighbor, relax low[u] with that node's discovery time.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A pure tree (E == n-1) has every edge critical
  • A single cycle has no critical connections
  • Deep graphs can exceed Python's default recursion limit
!

Common beginner mistakes

  • Skipping only the direct parent is correct here because the problem guarantees no repeated edges; with parallel edges you must skip by edge id, not by node
  • Updating low with low[v] for back-edges instead of disc[v] can miss bridges
  • Recursion depth up to 10^5 may need sys.setrecursionlimit or an explicit stack
Check your understanding

Why compare low[v] against disc[u] rather than low[u]?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#505The Maze IIWeighted shortest path on a grid#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#787Cheapest Flights Within K StopsShortest path with a hop limit#815Bus RoutesUnweighted shortest path (fewest transfers)