Find Bridges in Graph Using Tarjan's Algorithm (Time & Low Arrays)

Problem Statement❯

You are given a network of n servers numbered from 0 to n - 1 connected by undirected server-to-server connections, where each connection is represented as [a, b].

A critical connection is a connection that, if removed, will disconnect the network — making some servers unreachable from others.

Return all such critical connections in any order.

Note: In this problem, servers are treated as nodes of a graph, and connections as undirected edges. The goal is to find all bridges in the graph using Tarjan's Algorithm.

Examples❯

n	Connections	Output	Description
4	[[0,1],[1,2],[2,0],[1,3]]	[[1,3]]	Removing edge 1-3 disconnects node 3
5	[[0,1],[1,2],[2,3],[3,4],[4,2]]	[[0,1]]	Only 0-1 is a bridge; others are in a cycle
2	[[0,1]]	[[0,1]]	Single connection is always a bridge
3	[[0,1],[1,2],[2,0]]	[]	Fully connected triangle — no bridges
0	[]	[]	Empty graph, no edges or bridges

Solution❯

To find critical connections (bridges), we use Tarjan’s Algorithm, which applies DFS traversal and tracks two values for each node:

Time of insertion: The order in which the node is visited during DFS.
Low time: The lowest time reachable from that node (via back edges).

If for a node u and its neighbor v, we find that low[v] > tin[u], then the edge [u, v] is a bridge.

This approach ensures we detect edges that, if removed, would disconnect parts of the graph. We maintain:

A visited set to track visited nodes.
tin[]: time of insertion of each node.
low[]: lowest discovery time reachable from subtree rooted at a node.
A global timer to assign timestamps incrementally.

DFS recursively updates these values. If a neighbor is already visited (and not the parent), it indicates a back edge. If not visited, recurse into it and update low time accordingly.

Algorithm Steps❯

Initialize graph as an adjacency list.
Create arrays: tin[], low[] and visited[] of size n.
Set a timer = 0.
For each unvisited node, run DFS:

Mark node as visited, set tin[node] = low[node] = timer++.
For each neighbor:

If it is the parent, continue.
If not visited, recurse and update low[node].
If low[neighbor] > tin[node], then [node, neighbor] is a bridge.
If already visited, update low[node] = min(low[node], tin[neighbor]).

Code

JavaScript

function criticalConnections(n, connections) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of connections) {
    graph[u].push(v);
    graph[v].push(u);
  }

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

  function dfs(node, parent) {
    visited[node] = true;
    tin[node] = low[node] = timer++;

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

      if (!visited[neighbor]) {
        dfs(neighbor, node);
        low[node] = Math.min(low[node], low[neighbor]);

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

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i, -1);
    }
  }

  return bridges;
}

console.log("Bridges:", criticalConnections(4, [[0,1],[1,2],[2,0],[1,3]]));

⬅ Previous TopicMaking a Large Island Using DSU

Next Topic ⮕Articulation Points in Graphs