Я не знаю, баяном ли является то, что я придумал, но единственный алгоритм, который я нашел на емаксе, решает задачу при помощи Флойда-Уоршелла, который, как известно, работает за O(n3). Ниже приводится описание алгоритма, который работает за O(n*m).
Итак, суть задачи. У нас есть произвольный ориентированный граф с n вершинами и m ребрами, нужно найти все пары вершин, такие что путь между ними бесконечно мал.
Шаг 1. Из данного графа получим конденсацию.
Следующее утверждение: если в компоненте сильной связности есть цикл отрицательного веса, то между любой парой вершин из этой компоненты сильной связности есть бесконечно малый путь.
В самом деле, доберемся из начальной вершины до цикла - а это мы можем сделать, так как у нас компонента сильной связности, - пройдем по циклу любое произвольное число раз и перейдем в нашу вторую вершину - опять же, мы сможем это сделать в силу КСС.
Шаг 2. Итак, запустим Форда-Беллмана в каждой КСС. Он найдет нам отрицательный цикл, если он есть.
Шаг 3, а. Произведем серию поисков в ширину на 0-1 графе из каждой вершины полученной конденсации.
Давайте будем называть "черной" ту вершину конденсации, у которой внутри нее есть цикл отрицательного веса.
Утверждение: если в первоначальном графе между двумя вершинами есть путь, проходящий хотя бы через одну "черную" компоненту связности(включая компоненты связности этих двух вершин), то между двумя вершинами существует сколь угодно малый по величине путь.
Действительно, зайдем в эту компоненту связности, дойдем до цикла, проитерируемся по циклу любое произвольное число раз, и потом выйдем из цикла и дойдем до второй вершины.
Теперь как мы будем осуществлять поиск в ширину. Если первая вершина была черная, то перекрасим всех ее сыновей в черный цвет, и так далее. Иначе сначала переберем всех черных сыновей, и от них запустимся как раньше - покрасим всех сыновей черного сына в черный цвет. Очевидно, что все вершины, которые стали черными - между ними и начальной вершиной лежит вершина, в которой есть цикл отрицательного веса.
Шаг 3, б. Результаты обходов сохраним в матрице смежности.
Шаг 4. Для каждой пары вершин за O(1) найдем, в какой КСС они лежат, и по построенной матрице определим, лежит ли между ними цикл отрицательного веса, так же за O(1).
Асимптотическая сложность: по шагам: 1)O(n*logn) 2)O(n*m) 3)O(n1*m1); так как n1<=n и m1<=m, получим O(n*m). 4)O(n2).
То есть суммарно не более чем O(n*m)
Сложность по памяти: 0) начальный граф - O(m + n) 1) для хранения конденсированного графа O(m + n) и для каждой вершины ссылка на номер ее КСС - O(n) 2-3) под матрицу O(n1*n1) = O(n*n) 4) 0.
Итого O(n2 + 2*m + 3 * n)
Вопросы от автора:
1) это баян?
2) Видите ли вы какие-нибудь оптимизации? Особенно это касается оптимизации по памяти.
Реализация алгоритма - http://pastie.org/2774882
Можно вместо пункта 3 пустить динамику вида "множество достижимых компонент" вверх по конденсации (объединение по потомкам), и параллельно "множество компонент - ответов" (это либо объединение по потомкам, либо, если сама компонента черная, все достижимые). Будет то же, только битовое. И O(V^2) памяти (тоже битовой при желании).
То, что предлагает Narg работает за n*m, но находит только одну такую вершину. Если же добавлять ребра веса 0 из добавленной вершины, то если я правильно понял это вообще WA на тесте -1 получается.
Значит, плохо понял.
Объясняю подробнее:
1. Добавим фиктивную вершину = инициализируем расстояния 0.
2. Запускаем ФБ, запоминая предка каждой вершины.
3. После |V|-й итерации найдём все циклы в графе из рёбер вида (вершина, её предок). Для каждой компоненты верно, что если в ней есть отрицательный цикл, то какой-то из них найден.
4. Для каждой вершины v хотим сказать до каких вершин есть сколь угодно малый путь (это, кстати, не тоже самое, что "путь между ними бесконечно мал". Путь подразумевается кратчайший, но его не существует.). Для этого: найдём (обходом из v) вершины циклов, достижимых из неё. Запустим заново обход c них и будем выводить все посещенные вершины как ответ для v.
Итого: время O(|V| * |E|), память O(|V| + |E|), нет явного построения КСС.
Как же мы после n-й итерации найдем все циклы? По-моему, это неверно. Вот тест:
Но квадратной памяти всё равно не нужно. Ничего кроме разбиения на компоненты и пометок в какой есть цикл отрицательного веса не нужно, чтобы просто за n обходов вывести все пары вершин.
короче сдал 137 задачу на acmp.ru. Вот код, пока это быдлокод
Ну, видимо - не боян, но теперь стал им :)
Проблема этой задачи, наверное, в том, что не так-то просто отделить быстрый N^3 Флойда от NM достаточно навороченного алгоритма.
Нет, потому что мы знаем, что такое O и имеем некоторые представления о русском языке