pavlik 322, Алгоритмам топологической сортировки не надо, чтобы все было одним куском. Конкретно в алгоритме Кана у вас будут вершины без входящих ребер во всех кусках графа. Да, вершины из разных кусков могут в итоге быть в перемешку, но это ничего не портит.
pavlik 322, Можно, конечно, но это в N раз медленнее. Если считать степень, то у вас только один цикл по всем ребрам (или один по вершинам, другой по исходящим ребрам).
pavlik 322, Лучше используйте алгоритм Таръяна тут. Он сразу вам вершины будет снизу вверх выдавать. Как я описывал - функция считает вершину, рекурсивно считая то. что для нее нужно.
Алгоритм Кана работает как обход в ширину - берет сначала те вершины, которые в самом верху. Удаляет их из графа, потом опять берет вершины, которые в самом верху и т.д. Для этого нужна степень, ибо наверху те вершины, у которых входящая степень 0. Без счета степени оно не работает.
Можно ли таким образом обнаружить, что этот граф содержит изолированные узлы
У вас как-то свреху на голову все перевернуто. Для работы алгоритма надо найти "изолированные" узлы, а не в результате его работы вы их находите. Чтобы их найти надо подсчитать степени и пройтись циклом по всем вершинам, иначе никак.
pavlik 322, Потому что это не проще чем просто запустить обход от всех вершин. Ведь вам все равно обычно надо все корневые вершины еще и найти в графе. Так что это такой же цикл по всем вершинам, но при этом надо граф менять и как-то помнить, что вот эта новая вершина корень - фиктивная и где-то дальше ее отдельно обрабатывать.
pavlik 322, Если корневой узел один, то сразу ясно, откуда надо запускаться, и обход обойдет все вершины. Если их несколько, то нет гарантии, что один запуск обойдет все. Поэтому надо будет в цикле обходить все вершины и считать их, если они не подсчитаны.
pavlik 322,
Почитайте статьи про топологическую сортировку, все должно стать понятно.
Или смотрите на это с другой стороны. Функция считает значение в вершине. Если оно было уже подсчитано, то просто возвращает его. Иначе вызывается рекурсивно от всех детей, чтобы подсчитать их, применяет операцию в текущей вершине, сохраняет значение, и возвращает его.
pavlik 322, Для обхода в глубину и для топологической сортировки это не проблема. Раз у вас, судя по некоторым замечаниям, может быть несколько корневых вершин, то у вас будет топологическая сортировка, которая работает через обход в глубину. У вас там будут пометки вершин, в которых вы уже были, и обход не заходит в вершину второй раз.
есть более удобный способ, называется списком смежности. Вы для каждой вершины храните список всех вершин, в которые из нее есть ребра. При чем не обязательно использовать списки, это могут быть и массивы.
Алескей Дворяшин, Не может. Ведь p до 10^9, а оно влезает в 32-битный int. Соответственно, произведение двух таких чисел точно влезает в 64-битный тип.
pavlik 322, Давайте вот этот ваш пример разберем. У вас есть DAG, в каждой вершине которого или операция, или это лист с буквой. Так? У вас всегда в графе одна "корневая" вершина? Это запись арифметического выражения и вы хотите его посчитать, т.е. вам надо обойти все вершины в топологическом порядке снизу вверх?
Вычитание из всех строк не меняет оптитмальное назначение, потому что вы вычли число из всех строк. любое назначение берет по одному числу из каждой строки, а значит вы изменили стоимость всех назначений на одно и то же число (n*сколько прибавили к каждой строке). А значит оптимальное все еще остается назначением с минимальной стоимостью. Если вы возьмете и все цены в магазине уменьшите на 100рублей, самый дешевый товар остается самым дешевым.
alex_agaphe, Если потенциал равен нулю и, допустим, нулевых значений в A нет, тогда H пустое вообще. Жестких ребер в графе нет вообще. Никакой удлинняющей цепочки найти нельзя, потому что там должны быть ребра из H и M, а у нас они оба пустые в начале. Обход в графе обойдет все вершины слева и ни одной вершины справа. Z1={1..N}, Z2={}. Поэтому при вычислении дельта вы обходите вообще все значения матрицы. Читайте формулу внимательно, там все j НЕ принадлежащие Z2.
