Есть задачка:

http://acm.timus.ru/problem.aspx?space=1&num=1557

В ней нужно подсчитать кол-во способов удалить два различных ребра из связного графа, чтобы он перестал быть связным.

В комментариях я прочитал, что можно это сделать за n + m.

Я научился делать только за n * n.

Мое решение:

Рассмотрим дерево обхода dfs. Ребра разбились на 2 типа.(прямые и обратные)

Удалять 2 обратных нет смысла(Граф останется связным).

Удаляем прямое ребро и обратное. Это можно сделать, как при поиске мостов, только поддерживаем не только самую высокую ссылку на верх, а еще и вторую по высоте.

Удаляем 2 прямых ребра. Здесь мы просто перебираем два прямых ребра и смотрим разбился граф на два или нет.(Это делается, опять же при помощи поддержания нужных ссылок на верх.)

Это краткое описание моего решения. Но как делать быстрее?