10. Цикл в графе

Задача

По заданному неориентированному графу определите, существует ли в нём простой цикл нечётной длины, и выведите любой такой цикл.

Входные данные

В первой строке даны числа $n$ и $m$ ($1 \leqslant n \leqslant 100$, $0 \leqslant m \leqslant \tfrac{n(n-1)}{2}$) — количество вершин и рёбер. В следующих $m$ строках приведены пары различных чисел — вершины, соединённые ребром. Каждое ребро встречается не более одного раза.

Выходные данные

Если в графе нет цикла нечётной длины, выведите NO. Иначе выведите YES, затем длину найденного цикла и перечислите вершины в порядке обхода цикла.

Примеры

стандартный ввод      стандартный вывод
5 5                    NO
1 2
2 3
4 3
4 1
4 5

4 5                    YES
1 2                    3
2 3                    3 2 1
3 1
3 4
4 2

Ограничения

  • Время: 2 секунды
  • Память: 64 мегабайта
Редакционный разбор Параллельно проверке графа на двудольность можно восстановить нечётный цикл. Красим вершины DFS/BFS: стартовая вершина получает цвет $0$, её соседи — $1$, далее по модулю $2$. Когда встречаем ребро $(u, v)$, ведущее в уже окрашенную вершину того же цвета, мы нашли конфликт и, следовательно, нечётный цикл. Для восстановления цикла храним массив `parent`. Пусть `u` и `v` — конфликтующие вершины. Поднимаемся по родителям от обеих вершин, пока не встретим общую вершину $w$ (первый общий предок). Сохраняем цепочку `u → ... → w`, затем добавляем цепочку `w → ... → v` в обратном порядке и завершаем ребром `(v, u)`. Общая длина получается нечётной, потому что конфликт возник у вершин одного цвета. Если конфликтов нет, граф двудольный и ответ «NO». Ограничения позволяют хранить списки смежности и выполнять один DFS за $O(n + m)$.

Mentioned by