Есть задачка:
http://acm.timus.ru/problem.aspx?space=1&num=1557
В ней нужно подсчитать кол-во способов удалить два различных ребра из связного графа, чтобы он перестал быть связным.
В комментариях я прочитал, что можно это сделать за n + m.
Я научился делать только за n * n.
Мое решение:
Рассмотрим дерево обхода dfs. Ребра разбились на 2 типа.(прямые и обратные)
Удалять 2 обратных нет смысла(Граф останется связным).
Удаляем прямое ребро и обратное. Это можно сделать, как при поиске мостов, только поддерживаем не только самую высокую ссылку на верх, а еще и вторую по высоте.
Удаляем 2 прямых ребра. Здесь мы просто перебираем два прямых ребра и смотрим разбился граф на два или нет.(Это делается, опять же при помощи поддержания нужных ссылок на верх.)
Это краткое описание моего решения. Но как делать быстрее?
За O(N + M) не умею, но знаю, что решение за O(M * polylog(M, N)) рассказано тут.
Есть вероятностное решение, каждая итерация которого работает за линию (при этом итераций для хорошей вероятности надо не очень много). На первый взгляд, тут описана хотя бы его идея, но я не уверен.