How do you approach Critical Connections in a Network?

An edge is a bridge iff it does not lie on any cycle.

What is the time complexity of Critical Connections in a Network?

Time complexity: O(V + E). Space complexity: O(V + E) for the adjacency list and recursion.

What are common mistakes on Critical Connections in a Network?

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

gitGood.dev

← Back to problems

Critical Connections in a Network

HardAlgorithms

Description

There are `n` servers numbered from `0` to `n - 1` connected by undirected server-to-server `connections` forming a network where `connections[i] = [a_i, b_i]` represents a connection between servers `a_i` and `b_i`. 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.

Example 1

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

Output: [[1,3]]

Explanation: [[3,1]] is also accepted. Removing edge (1,3) disconnects server 3 from the rest.

Example 2

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

Output: [[0,1]]

Constraints

- 2 <= n <= 10^5 - n - 1 <= connections.length <= 10^5 - 0 <= a_i, b_i <= n - 1 - a_i != b_i - There are no repeated connections.

Critical Connections in a Network: approach, complexity and pitfalls

A hard graphs problem, graded against 5 test cases (2 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

More Graphsproblems →

If you are stuck

Show the 3-step hint ladder

An edge is a bridge iff it does not lie on any cycle.
Use Tarjan's algorithm: track discovery time `disc[u]` and the lowest discovery time `low[u]` reachable from the subtree rooted at u.
Edge (u, v) is critical iff low[v] > disc[u] - i.e., v's subtree has no back-edge reaching u or above.

The optimal approach

Show the approach: Tarjan's Bridge-Finding DFS

Run a DFS, assigning each node a discovery timestamp `disc[u]` and tracking `low[u]` = the smallest `disc` value reachable from u via tree edges followed by at most one back edge. For a tree edge (u, v), the edge is a *bridge* iff `low[v] > disc[u]` - that means v's subtree cannot reach u or any ancestor of u except through (u, v) itself, so removing it disconnects the graph. Skip the immediate parent when scanning neighbors so we don't mistake the edge we came in on for a back edge. Note: with multi-edges between u and v we'd need an edge-id check instead of a parent check, but the constraint `no repeated connections` rules that out.

Time: O(V + E)
Space: O(V + E) for the adjacency list and recursion

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.