The problem
Given an undirected network of servers, return every connection (edge) whose removal would disconnect the network — the bridges of the graph.
Stuck? Reveal hints one at a time
How to approach it
- 1Build an adjacency list and run one DFS, stamping each node with an increasing discovery time.
- 2Compute low[u]: the minimum of u’s own time, the low of each child, and disc of each back-edge target (skipping the edge back to the parent).
- 3After recursing into child v, if low[v] > disc[u], record (u, v) as a bridge.
- 4Return all recorded bridges.
Key insight
low[v] > disc[u] literally reads: "nothing in v’s subtree can reach u or anything older than u without using this edge" — the definition of a bridge.
The solution
Watch out for
- Skipping the parent edge only once matters when parallel edges exist; here the parent check suffices for simple graphs.
- Deep recursion can overflow the stack in Python — raise the recursion limit or go iterative.