Graph Theory37 sections · 1633 units
Open in Course

Bridge Detection Logic

(When is an edge a bridge?)

For each tree edge (u,v)(u, v) where uu is the parent of vv in the DFS tree: Check if low[v] > disc[u]. If yes, (u,v)(u, v) is a bridge. Why? low[v] > disc[u] means the subtree of vv cannot reach uu or any ancestor of uu.

The edge (u,v)(u, v) is the only connection between the subtree and the rest of the graph. If low[v] <= disc[u], then there is a back edge providing an alternate path, so (u,v)(u, v) is not a bridge.