Critical Wires — Solution & Editorial

Back to the Problem

Tarjan lowlink over a DFS forest: edge (parent, u) is a bridge iff low[u] > disc[parent]. Track the parent EDGE ID (not the parent node) so multi-edges are handled; iterate, don't recurse.

Complexity: O(N + M)

Watch out: Skipping the parent NODE instead of the parent EDGE mishandles doubled edges — they are not bridges.