Дистанционная подготовка: Вопрос о сложности алгоритма и времени выполнения
Вопрос о сложности алгоритма и времени выполнения
от Julia Zhavoronkova - Четверг 20 Ноябрь 2014, 02:01
1333. Долой списывание!
  Вопрос такой.
В задаче необходимо определить, существует ли в графе хотя бы один простой цикл нечетной длины, либо все простые циклы - четной длины.
Для этого необходимо пройтись по всем простым циклам в графе и сосчитать их длину. Сложность алгоритма при n вершинах будет O(n!), так?
В моей программе на тестах 13-17 выдается ошибка - "Превышено максимальное время работы".
Правильный ли подход я использую и как можно было бы мне уменьшить время выполнения?
Re: Вопрос о сложности алгоритма и времени выполнения
от Peter Cherepanov - Четверг 20 Ноябрь 2014, 07:51
  Нет тут никаких факториалов. Нужно обойти граф и красить вершины в 2 цвета попеременно. Если встретится покрашенная вершина (т.е. цикл), то проверить, что она покрашена в нужный цвет. Время работы такого алгоритма пропорционально числу дуг в графе.