394. Find Bridges in a Graph

Given an undirected graph with n vertices (0-indexed) and m edges, find every bridge - an edge whose removal increases the number of connected components. Print each bridge as 'u v' with u < v, one per line, sorted in ascending order of (u, v); print 'None' if there are no bridges.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains two integers, an undirected edge. Output: Print each bridge as 'u v' (u < v) on its own line, sorted in ascending order; print 'None' if there are no bridges.

1 <= n <= 10^5

When a graph has MULTIPLE edges between the same pair of vertices, treating them as indistinguishable (just by endpoints) can incorrectly suppress a genuine bridge - tracking edges by their own unique ID (so the 'don't go back along the parent edge' rule only skips THAT specific edge, not any edge to the parent) avoids this subtle bug.

Find every edge in an undirected graph whose removal would increase the number of connected components. Brute force: For every single edge, REMOVE it temporarily and check if the graph's component count increases - this costs O(m * (n+m)), far too slow for large graphs, when a single DFS pass with discovery/low tracking finds all bridges in linear time. Optimised: The discovery-time/low-value DFS technique computes, for every vertex, the EARLIEST-discovered vertex reachable via any back-edge from its ENTIRE subtree - an edge is a bridge exactly when its child's subtree has NO way to reach back past the edge itself, a condition checkable in O(1) per edge once discovery/low values are computed, avoiding any need to actually remove edges and re-check connectivity.

Do one DFS computing, for every vertex, its discovery time disc[] and its low-link value low[], the lowest discovery time reachable from that vertex's subtree using at most one back edge. A tree edge (u, v) is a bridge exactly when low[v] is strictly greater than disc[u], meaning v's subtree has no back edge reaching u or any ancestor of u. This finds every bridge in a single linear pass with no repeated traversals or edge-versus-edge checks at all. Time: O(n+m) Space: O(n+m)

For every edge, temporarily remove it from the graph and run a BFS or DFS to check whether its two endpoints are still connected to each other through some other path; if they're no longer connected, that edge is a bridge. This directly implements the definition of a bridge, an edge whose removal increases the number of connected components, but it re-traverses the whole graph once for every single edge. Time: O(m*(n+m)) Space: O(n+m)

Run a single DFS to build a DFS tree with discovery times, classifying every non-tree edge as a back edge. Then, for every tree edge connecting parent u to child v, check whether any back edge connects a vertex inside v's subtree to a proper ancestor of u; if at least one such back edge exists, that tree edge is 'covered' and is not a bridge, otherwise it is. Scanning all back edges against every tree edge still costs extra work, but this replaces the brute force's repeated full graph traversals with a single DFS plus targeted subtree checks. Time: O(n*m) Space: O(n+m)

1. Run a DFS tracking each vertex's DISCOVERY TIME and its 'LOW' value (the smallest discovery time reachable from it using AT MOST ONE back-edge). 2. An edge (u,v) in the DFS tree is a BRIDGE exactly when low[v] > disc[u] - meaning v's entire subtree has NO other way back up to u or above. 3. Skip going back along the exact PARENT edge you just came down (but treat multiple edges between the same pair as DISTINCT by their own id, not just by endpoints, or a genuine bridge could get incorrectly masked).

Time: O(n + m) - a single DFS pass computing discovery times and low values for every vertex. Space: O(n + m), for the DFS recursion stack, discovery/low arrays, and the graph itself.

Test a graph with no bridges at all (print 'None'), multiple edges between the same pair of vertices (which shouldn't be mistaken for a bridge), and n at the upper bound of 10^5.

Be ready to explain the low[v] > disc[u] bridge condition precisely with a small example - this is one of the more subtle DFS-based algorithms, and clearly articulating WHY this condition identifies a bridge (v's subtree is 'cut off' with no back-edge escape) is a strong signal.