The idea
A bridge is an edge whose removal splits the graph; an articulation point is a vertex with the same effect.
Run one DFS and record num[u], the time u was first visited, and low[u], the smallest num reachable from u’s subtree using at most one edge that goes back up.
A tree edge u → v is a bridge when low[v] > num[u]: nothing below v reaches u or above. A non-root u is an articulation point when some child has low[v] ≥ num[u]; the root is one when it has two or more DFS children.
Sample problem
1192. Critical Connections in a Network ↗ Hard
Servers are connected by undirected links, and the network is connected. A link is critical if removing it disconnects some servers. Return all critical links.
n = 5, connections = [[0,1],[1,2],[2,0],[1,3],[3,4]] output = [[3,4],[1,3]]
Why the solution works
Removing each link and testing connectivity is O(E · (V + E)). One DFS is enough.
The DFS turns the graph into a tree plus edges that jump back up to an ancestor. A tree edge u → v survives being removed only if something in v’s subtree can jump back to u or above.
low[v] records the highest point that subtree can reach. If low[v] > num[u], it cannot reach u, and the edge u–v is a bridge.
Complexity: O(V + E) time and memory.
Watch out
- With parallel edges, skipping by parent vertex is wrong: skip the edge you came along by its id.
- The root needs its own rule for articulation points.
- Update
lowwithnum[v]on a back edge and withlow[v]after a tree edge.