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.

Algorithm Steps

1. Initialize graph as an adjacency list.
2. Create arrays: tin[], low[] and visited[] of size n.
3. Set a timer = 0.
4. For each unvisited node, run DFS:
1. Mark node as visited, set tin[node] = low[node] = timer++.
2. For each neighbor:
1. If it is the parent, continue.
2. If not visited, recurse and update low[node].
3. If low[neighbor] > tin[node], then [node, neighbor] is a bridge.
4. If already visited, update low[node] = min(low[node], tin[neighbor]).

Code

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]]));