Bridges in Graph

Find all critical edges whose removal disconnects the graph.

graph dfs bridges connectivity

In an undirected connected graph, an edge is called a bridge (or cut edge) if removing it increases the number of connected components. Given the number of vertices `n` (vertices labeled 0 to n-1) and a list of edges (each edge is a list of two integers), implement the function `find_bridges(n, edges)` that returns a list of lists, each inner list being [a, b] where a < b, representing all bridges in the graph. The graph is simple, undirected, and connected. The output list should be sorted lexicographically (i.e., by the first vertex, then by the second vertex).

Constraints

- 2 <= n <= 1000
- 0 <= len(edges) <= 10000 (graph may be empty only if n == 1, but connected property ensures no isolated vertices for n >= 2)
- The graph is connected.
- No self-loops or parallel edges.
- Time complexity: O(n + m) where m is the number of edges.
- Space complexity: O(n + m).

Example

>>> find_bridges(5, [[0,1],[0,2],[1,2],[1,3],[3,4]])
[[1,3],[3,4]]
>>> find_bridges(2, [[0,1]])
[[0,1]]
>>> find_bridges(3, [[0,1],[1,2]])
[[0,1],[1,2]]

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use DFS to compute discovery and low-link values.

An edge (u,v) is a bridge if low[v] > disc[u] when exploring v from u.

Remember to output each bridge as [min, max] and sort the final list.

Track parent vertex to avoid undoing reverse edge.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.