Graph BFS / DFS
LC #1192Hard
Critical Connections in a Network
Graph BFS / DFS
AmazonGoogleMetaBloombergProblem
Find all critical connections (bridges) in a network — edges whose removal disconnects the graph.
graphdfstarjan
Constraints
- ›2 ≤ n ≤ 10⁵
- ›n-1 ≤ connections.length ≤ 10⁵
- ›No repeated connections, no self-loops
Example
Input
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]Output
[[1,3]]Why
Removing [1,3] disconnects node 3. All other edges are part of a cycle.