Skip to main content

1192. Critical Connections in a Network

hard

Find every edge whose removal disconnects the network — the bridges of an undirected graph. Tarjan's bridge-finding algorithm in one DFS pass using discovery times and low-link values.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network. A critical connection is a connection that, if removed, will make some servers unable to reach some other server. Return all critical connections in the network in any order.

Constraints

  • 2 <= n <= 10^5
  • n - 1 <= connections.length <= 10^5
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • There are no repeated connections.

Examples

Example 1

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

Explanation: [[3,1]] is also accepted. Edge 1-3 is the only bridge — removing any of the other edges leaves the graph connected via the cycle 0-1-2.

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The naive approach removes each edge and tests connectivity — that's O(E * (V + E)) and too slow.

Hint 2

An edge (u, v) is a bridge iff there's no back-edge from the subtree rooted at v to u or an ancestor of u. Sounds like a job for DFS discovery times.

Hint 3

Tarjan's algorithm: in one DFS, track disc[node] (time of first visit) and low[node] (lowest disc reachable via the subtree plus one back-edge). Edge (u, v) is a bridge when low[v] > disc[u].

Solution approach

Reveal approach

Tarjan's bridge-finding algorithm. Build an adjacency list. Run a single DFS that maintains two per-node values: disc[u] (the timestamp when DFS first visits u) and low[u] (the smallest disc reachable from u's subtree, possibly using one back-edge). Initialize low[u] = disc[u] when first visited. For each neighbor v of u: if v is the parent, skip; if v is unvisited, recurse, then low[u] = min(low[u], low[v]) and if low[v] > disc[u], record (u, v) as a bridge; if v is already visited (back-edge), low[u] = min(low[u], disc[v]). The intuition: low[v] > disc[u] means v's subtree has no alternate path back to u or above, so the edge (u, v) is the only way to reach v's subtree. Watch the parent-edge handling for multigraphs (count parent occurrences) — for this problem (no duplicate edges) skipping by parent ID is fine. O(V + E) time, O(V + E) space.

Complexity

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

Related patterns

  • graph-dfs
  • tarjans
  • bridges
  • biconnected-components

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Critical Connections in a Network and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →