Critical Connections - Algorithm

$1.$ Build an adjacency list from the connections.

$2.$ Initialize disc[v] = -1 for all $v$ (unvisited marker), low[v] = 0, $timer = 0$, $result = []$.

$3.$ For each unvisited vertex, run DFS:

• Set disc[v] = low[v] = timer, $timer{+}{+}$
• For each neighbor $w$: if unvisited, recurse and update low[v]; if visited (not parent), update low[v] with disc[w]
• If low[w] > disc[v], add $(v, w)$ to result

$4.$ Return result.

This runs in $O(V + E)$ time and uses $O(V)$ space.