Дистанционная подготовка: Вопрос о сложности алгоритма и времени выполнения
Re: Вопрос о сложности алгоритма и времени выполнения
от Peter Cherepanov - Четверг 20 Ноябрь 2014, 07:51
  Нет тут никаких факториалов. Нужно обойти граф и красить вершины в 2 цвета попеременно. Если встретится покрашенная вершина (т.е. цикл), то проверить, что она покрашена в нужный цвет. Время работы такого алгоритма пропорционально числу дуг в графе.