DiffPush Tier Graphs · Other Algorithms O(V + E) · O(V + E)
A datacentre's redundant links form a mesh, but some links are load-bearing: cut one and part of the cluster goes dark. Auditors call these bridges, and Tarjan's sweep finds them in one pass — a link is critical exactly when the subtree beyond it can never climb back to an earlier-discovered node.
Input: An integer n (servers 0..n-1) and a list connections where [a, b] is an undirected link.
Output: Return all critical links as pairs, in any order.
2 <= n <= 10^51 <= connections.length <= 10^5No duplicate or self linksInput: {"n":4,"connections":[[0,1],[1,2],[2,0],[1,3]]}
Output: [[1,3]]
The 0-1-2 triangle is self-sustaining; only the spur to server 3 is load-bearing.
Input: {"n":2,"connections":[[0,1]]}
Output: [[0,1]]
With one link and two servers, cutting it isolates both — maximally critical.