Bridges in a Graph

Given a connected undirected graph with vertexCount vertices numbered 0 through vertexCount-1 and an edge list, return every bridge as an endpoint pair. A…

Given a connected undirected graph with vertexCount vertices numbered 0 through vertexCount-1 and an edge list, return every bridge as an endpoint pair. A bridge is an edge occurrence whose removal disconnects the graph. Return pairs in any order and either endpoint orientation. Return [] when there are no bridges. Parallel edge occurrences and self-loops are allowed; removing just one parallel occurrence does not remove its other copies. Do not modify the input.

- 2 <= vertexCount <= 10000 - 2 <= edges.length <= 10000 - Each edge contains exactly two integer endpoints in 0..vertexCount-1 - The graph is connected; parallel edges, reversed duplicate occurrences and self-loops are allowed - Return every bridge once; pair order and endpoint orientation are irrelevant - The preset visualizer uses at most 24 vertices and 48 edge occurrences; full-sized valid inputs remain execution-only

Example 1: input vertexCount = 4, edges = [[0,1],[1,2],[2,0],[1,3]]; output [[1,3]]. The triangle remains connected after any one of its edges is removed. Removing the edge between 1 and 3 isolates vertex 3, so only that edge is a bridge.

Example 2: input vertexCount = 3, edges = [[0,1],[1,2],[2,0]]; output []. Each edge has an alternate route around the triangle. Removing any one edge leaves all vertices connected.

Category: Graphs. Topic: graph. Difficulty: Hard. Patterns: graph-traversal.