Раз уж все в задачи ударились.. Куда конь с копытом, туда и рак с клешней Дан произвольный ориентированный граф. Мы раскрашиваем его следующим образом: 0) i = 1 1) Берем какой-нибудь еще не раскрашенный узел A_i и еще не использованный цвет M_i. Красим A_i в цвет M_i. 2) Для каждого узла цвета M_i раскрашиваем всех его бесцветных последователей тоже в цвет M_i. 3) Повторяем шаг 2), пока есть, что раскрашивать. 4) Если еще остались бесцветные узлы, то переходим к 1), выбирая следующие A_(i+1) и M_(i+1). То есть в итоге мы имеем серию начальных узлов A1, A2,...,An, раскрашивающих граф в n цветов. Вопрос: как нужно выбирать эти начальные узлы, чтобы n получилось минимальным? Интересует оптимальный по скорости алгоритм.
Stiver Чтобы n получилось минимальным, нужно выбирать те узлы, в которые нельзя попасть из других. В узлах счётчик ссылок можно хранить?
Black_mirror Не обязательно, граф же ориентированный. Пример: Узлы: 1,2,3,4,5,6,7 Ребра: 1->2, 2->3, 3->1, 5->6, 6->7, 7->5, 2->4, 6->4
Stiver В общем мне кажется что в алгоритм между 0м и 1м пунктом нужно добавить еще один такой же цикл, только покраску в нём начинать с тех вершин, в которые входит 0 рёбер.
Black_mirror Не понимаю.. Зачем нужно? Узел без входящих ребер - это частный случай узла вообще. Значит этот цикл уже содержится в приведенном мною. Вопрос был про алгоритм выбора начальных узлов A_i, ограничиться здесь узлами без входящих ребер не получится (см. мой пример выше)
Stiver Я наконец-то понял условие этой задачи. 1) Находим все сильносвязные компоненты графа: http://rain.ifmo.ru/~orybak/scc/doc/SearchScc-Algorithm.html 2) Считаем количество ссылок на каждую компоненту из других компонент. 3) Ну и начинаем красить с тех компонент, на которые нету ссылок из других.
У меня карсач был по дискре такой-же. Банальный метод ветвей и границ. С кучей эвристик и хитростей. Один абзацем не описать, но задача не особо красивая.
Proteus Думаю, у тебя было что-то другое, так как тут никаких эвристик и хитростей точно не надо. Black_mirror Отлично! Действительно, по отношению к операции раскрашивания сильносвязные компоненты будут аналогом узлов. Можно сказать, что граф берется по модулю раскрашивания и сильносвязные компоненты будут своеобразными классами вычетов. Но с точки зрения скорости это не совсем оптимальное решение. Если правильно помню, то поиск сильносвязных компонентов дает в худщем случае квадратное время O(n^2). Можно разложить граф на непересекающиеся подмножества с представителями (каждое из которых получит свой цвет) с помощью union-find структуры, тогда получим линейную сложность. Кстати была высказана здравая мысль, добавлять к описанию задачи источник и причину возникновения. Первопроходец The_Svin правда отбрыкивался от объяснений, ссылаясь на производственные тайны, но большинство задач имеют все-таки более тривиальную историю. В данном случае речь шла изначально об организации итераций на control flow graph метода. Для прямой итерации узлы как известно располагаются в порядке reverse post order. В случае же обратной итерации, от конца к началу, дело обстоит сложнее. Точка входа есть у любого метода и для любого блока существует путь от входа до него (иначе это мертвый код, который можно убрать). Но точку выхода программа вовсе не обязана иметь, она вполне имеет право содержать бесконечные циклы. Поэтому для построения rpr-order ("reverse post reverse order", термин мой ) нужно понять, с каких блоков начинать обход. Это и есть наша задача, хотя и немного по-другому сформулированная.
Stiver Сильносвязные компоненты ищутся одним поиском в глубину, т.е. за O(N+M). В общем, оптимальный (асимптотически) алгоритм.
