Если я правильно понял о чём идёт речь, то можно рассуждать следующим образом
Да, в таком смысле так.
Как-то сталкивался с задачей, где были циклы, но небольшие, компоненты сильной связности были не больше 10
Тут принципиальная разница, ибо какая бы у вас формула не была и каким бы не был граф, пока граф ациклический, у вас работает один и тот же алгоритм. Можно универсальный солвер написать, который принимает граф ифункцию. Он и называется ДП. Если же есть циклы, то там уже в зависимости от конкретной формулы и формы циклов будет свой уникальный алгоритм решения. Поэтому эти решения некороректно считать ДП.
art_gara55555, Почему у вас все кнопки обрабатываются в switch, а BUTTON_ID_CLOSE_SERVICE - отдельно в конце? Теперь этот кусок кода сработает по любому WM_COMMAND, даже если там не BN_CLICKED
. Вообще, в ациклическом графе циклов нет по определению. "ациклический" же, т.е. без циклов. Это опечатка же? Вы имели ввиду просто ориентированный граф?
pavlik 322, Потому что это высокоуровневое объяснения сути алгоритма. Для быстрой реализации вам надо поддерживать счетчики входящих ребер и очередь вершин, в которых A(v)=0. Подсчитайте входящие степени. Изначально кладите в очередь все корневые вершины (степень 0). Потом доставайте из очереди вершину, выводите ее в ответ, вычитайте 1 из счетчиков и кладите в очередь те вершины, где счетчики стали 0.
Если делать совсем наивно, то да, там получается еще два цикла.
pavlik 322, Приведите опять код, я запутался. У вас там выше был проход по узлам и потом проход по всем ребрам, а не только по ребрам, выходящим из текущей вершины. В этом ключевая разница. Вы каждое ребро обработаете для каждой вершины. Т.е. получается O(VE) = O(N^3). Если же обходить только ребра исходящие из заданной вершины, то каждое ребро обойдется только один раз.
pavlik 322, Да. Если граф полный (по N-1 ребра у каждого узла), то DFS в нем работает за O(N^2). Быстрее никак. Все ребра все равно придется посмотреть
pavlik 322, Нет, он O(V+E). Внешний цикл по вершинам. Внутри цикл по ребрам исходящим из данной вершины. Поэтому оно обойдет все вершины по одному разу и в каждой обойдет все ребра из нее. Суммарно E ребер.
pavlik 322, Алгоритмам топологической сортировки не надо, чтобы все было одним куском. Конкретно в алгоритме Кана у вас будут вершины без входящих ребер во всех кусках графа. Да, вершины из разных кусков могут в итоге быть в перемешку, но это ничего не портит.
pavlik 322, Можно, конечно, но это в N раз медленнее. Если считать степень, то у вас только один цикл по всем ребрам (или один по вершинам, другой по исходящим ребрам).
