Привет!
Не получается придумать оптимальное решение для следующей задачи: дан ориентированный граф (городов), вершины пронумерованы по DFS (pre-order).
Говорим, что город w снабжает город v, если все пути из корня (вершины 1) в v проходят через w.
Для каждого города нужно посчитать количество городов, которые он снабжает. Всего городов 1000, дорог (однонаправленных рёбер) 2000. Решить можно в лоб, перечисляя все пути через BFS или DFS, но это экспонента, не годится.
Думал о всяких рекурсивных методах, имея в виду такое наблюдение: если город w не снабжает город v, то он не снабжает и всех потомков v.
А нельзя по очереди удалять вершины и говорить что w снабжает v если до удаления v было достижимо, а после удаления перестало? Это должно за квадрат работать.
Хм, ну, не за квадрат, потому что матрицу достижимости ещё надо за куб построить (алгоритм Флойда-Уоршелла), но надо попробовать...
Ну тогда уж V Дейкстр с кучей за VElogE
Стоп а зачем?
Запустим dfs(1) и запомним все посещенные вершины. После удаления еще раз запустим dfs(1) и сравним
О, а это ведь очевидная мысль... Сейчас попробую.
А ещё надо ведь перестраивать матрицу достижимости для графа с удалённой вершиной каждый (квадрат) раз...
Почему?
Просто сделаем dfs(v,w) который сразу вырубается если v==w.
Можно попробовать посчитать ДП, сколько способов добраться от вершины i до j. Тогда город w будет снабжать город v, если dp1v = dp1w·dpwv
А как считать количество путей на циклическом графе?
В общем, задача была решена последовательным запуском dfs с пропуском каждой из вершин. Выходит, за квадрат о_О
При этом, как оказалось, я не до конца понял условие, и там ещё важно, что если несколько городов удовлетворяют условию снабжения, то выбирается один с наибольшим номером, поэтому идти надо от последнего к первому, запоминая города, которые кем-то уже снабжены.
Спасибо grikukan! =)
Линейным алгоритмом находишь все точки сочленения. А дальше все понятно. http://e-maxx.ru/algo/cutpoints