Поиск мостов и точек сочленения
Сформулируем задачу о поиске мостов и точек сочленения.
Мостом в связном неориентированном графе называется такое ребро $(v, u)$, что при удалении этого ребра из графа нарушается его связность. Точкой сочленения называется такая вершина $v$, что при удалении из графа вершины $v$ (и всех смежных ребер) он теряет свою связность.
Чтобы найти мосты, сделаем обход графа с помощью dfs. Этот обход построит нам какое-то остовное дерево графа (не путать с минимальным остовным деревом). Все ребра, по которым мы не сделали переход, будут вести от вершины остовного дерева к какому-то из предков. Заметим, что эти ребра не могут быть мостами --- при их удалении остовное дерево остается невредимым. Значит, мосты --- это какие-то из ребер остовного дерева.
Ребро $u \rightarrow v$ будет являться мостом, если из его поддерева нет ребер, которые ведут выше, чем $v$. Для того, чтобы узнать о существовании таких, для каждой вершины храним величину $fup_v$ -- минимальная высота вершины, в которую можно добраться из поддерева вершины $v$.
$$fup_v = \min(h_v, \displaystyle \min_{to \in subtree(v)} fup_to, \displaystyle \min_{to \in G(v), h_{to} < h_v, to \neq parent(v)} h_{to}))$$