Задача 4 — Какое ребро удалить, чтобы граф стал деревом
Связный неориентированный граф на N вершинах и N рёбрах. Найти ребро, удаление которого делает граф деревом.
Идея. Дерево на N вершинах имеет N−1 ребро. Здесь рёбер ровно N → есть ровно один цикл. Любое ребро этого цикла можно удалить. Ищем цикл обходом DFS: как только встречаем «обратное ребро» в серую вершину — мы внутри цикла, восстанавливаем его по стеку.