Find All Bridge Edges in an Undirected Graph
Problem statement
You are given an undirected graph $G = (V, E)$ with $n = |V|$ vertices and $m = |E|$ edges. A bridge is an edge whose removal disconnects the graph (increases the number of connected components).
Design an algorithm to find all bridges in $G$ in $O(n + m)$ time and $O(n)$ space.
Constraints:
- $1 \le n \le 10^5$
- $0 \le m \le 2 \times 10^5$
- The graph may be disconnected
- No self-loops, but parallel edges are possible
Example 1:
Input: $n = 5$, edges $= [(0,1), (1,2), (2,0), (2,3), (3,4)]$
Output: $[(2,3), (3,4)]$
Explanation: Removing edge $(2,3)$ disconnects vertex $3$ and $4$ from the rest. Removing $(3,4)$ disconnects vertex $4$. Edges $(0,1)$, $(1,2)$, and $(2,0)$ form a cycle, so none of them are bridges.
Example 2:
Input: $n = 4$, edges $= [(0,1), (1,2), (2,3)]$
Output: $[(0,1), (1,2), (2,3)]$
Explanation: This is a path graph with no cycles. Every edge is a bridge.
Example 3:
Input: $n = 3$, edges $= [(0,1), (1,2), (2,0)]$
Output: $[]$
Explanation: The entire graph is a single cycle. No edge is a bridge because every pair of vertices remains connected after any single edge removal.
Show hint
When you remove an edge, what structure around that edge would guarantee its two endpoints stay connected, and which traversal exposes that structure in one pass?
Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.
Related free problems
- Bridge and Torch with a Pairing ConstraintLinear Algebra & OptimizationMedium