hard

Critical Connections in a Network

Find every bridge in a network using discovery times and low-link values from a single depth-first walk.

1. Define the problem

Critical Connections in a Network

There are n servers numbered 0 to n - 1, joined by two-way connections. A connection is critical if removing it would leave some server unable to reach some other server. Return every critical connection, in any order. Such an edge is also called a bridge . Walk the network depth first and stamp every server with the time you first arrived . Then work out, for each server, the earliest arrival time anything in its part of the walk can reach by going backwards. If the best a neighbour can do is later than your own arrival time, nothing down there loops back past you, so the edge between you is a bridge.

Constraints

  • 2 ≤ n ≤ 105
  • n - 1 ≤ connections.length ≤ 105
  • No connection is repeated and no server is joined to itself
  • The network starts out connected

Example

Inputn = 4, connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
Output[[1, 3]]

Explanation Servers 0, 1 and 2 sit in a triangle, so any one of those edges can be cut and they still reach each other. Server 3 hangs off server 1 by a single edge, so that edge is critical.

2. Know the words first

In plain terms

Bridge
An edge whose removal splits the graph into more pieces than before. Every critical connection is a bridge.
Discovery time
A counter stamped on each node the first time the depth-first walk arrives there. Earlier numbers mean the node was reached sooner.
Low-link value
The smallest discovery time reachable from a node, using its own subtree plus at most one edge back up. If a neighbour cannot reach past you, the edge to it is a bridge.
Back edge
An edge that leads to a node already visited. A back edge is the only way a deeper node can reach an earlier discovery time.
3. Visualize the solution

One cell per server, value = discovery time / low-link value

One cell per server, value = discovery time / low-link value
Statusinit

Four servers, nothing visited, and the clock starts at zero.

What happens in this step

connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
discovery and low = unset for all four servers
timer = 0
bridges = []

Servers 0, 1 and 2 form a triangle; server 3 hangs off server 1.
Step 1 of 7

Steps to visualize

  1. The row has one cell per server. The value is written as discovery time, then a slash, then the low-link value.
  2. A dash means the walk has not reached that server yet.
  3. Arriving at a server stamps both numbers with the current clock reading.
  4. Meeting an already visited server pulls the low-link value down towards that server’s earlier discovery time.
  5. Coming back up an edge, if the child’s low-link is still larger than the parent’s discovery time, that edge is a bridge.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per server, value = discovery time / low-link value
Statusinit

Four servers, nothing visited, and the clock starts at zero.

What happens in this step

connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
discovery and low = unset for all four servers
timer = 0
bridges = []

Servers 0, 1 and 2 form a triangle; server 3 hangs off server 1.
Step 1 of 7
5. Solution

Solution

solution.tsTypeScript
function criticalConnections(n, connections) {
  const graph = Array.from({ length: n }, () => []);

  for (const edge of connections) {
    graph[edge[0]].push(edge[1]);
    graph[edge[1]].push(edge[0]);
  }

  const discovery = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const bridges = [];
  let timer = 0;

  function dfs(node, parent) {
    discovery[node] = timer;
    low[node] = timer;
    timer += 1;

    for (const next of graph[node]) {
      if (next === parent) continue;

      if (discovery[next] === -1) {
        dfs(next, node);
        low[node] = Math.min(low[node], low[next]);

        if (low[next] > discovery[node]) {
          bridges.push([node, next]);
        }
      } else {
        low[node] = Math.min(low[node], discovery[next]);
      }
    }
  }

  for (let node = 0; node < n; node++) {
    if (discovery[node] === -1) {
      dfs(node, -1);
    }
  }

  return bridges;
}
Time
O(n + e), where e is the number of connections
Space
O(n + e)
6. Test cases

Test cases

InputExpectedCovers
n = 4, connections = [[0, 1], [1, 2], [2, 0], [1, 3]][[1, 3]]example from the docstring, a triangle with one tail
n = 2, connections = [[0, 1]][[0, 1]]smallest network, where the only edge is critical
n = 4, connections = [[0, 1], [1, 2], [2, 3]][[0, 1], [1, 2], [2, 3]]a chain, where every single edge is critical
n = 3, connections = [[0, 1], [1, 2], [2, 0]][]a ring with no critical edge at all
n = 6, connections = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3]][[1, 3]]two rings joined by a single edge
n = 5, connections = [[0, 1], [1, 2], [3, 4]][[0, 1], [1, 2], [3, 4]]a network already in two pieces, so the outer loop restarts

Keep reading