e-olymp 2270. Поиск цикла

Задача

Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них.

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

В первой строке находятся два натуральных числа $n$ и $m$ $($$1$ $\leqslant$ $n$ $\leqslant$ $10$$5$$, $$1$ $\leqslant$ $m$ $\leqslant$ $10$$5$$)$ — количество вершин и ребер в графе соответственно. Далее в $m$ строках перечислены рёбра графа. Каждое задаётся парой чисел — номерами начальной и конечной вершин соответственно.

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

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

Тесты

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

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

1
2 2
1 2
1 2
NO
2 2 2
1 2
2 1
YES
1 2
3 4 4
1 4
2 3
3 2
1 4
YES
2 3
4 6 6
1 3
2 4
3 4
1 2
3 5
3 6
NO
5 4 4
1 3
4 2
2 3
3 4
YES
4 2 3

Решение

Для решения данной задачи воспользуемся поиском в глубину. Также будем «красить» вершины в различные цвета ($1$ (белый) — мы еще не посещали вершину, $2$ (серый) — посетили вершину и зациклились, $3$ (черный) — посетили вершину и вышли из неё).

В векторе $M$ будем хранить сам граф, а для самой проверки на цикличность воспользуемся векторами $visited$ и $colours$, в первом будем отмечать посещали ли мы вершину ранее или нет, во втором же изначально будут хранится только $1$
(белые) вершины, далее, по мере поиска, они будут приобретать другие цвета. И если мы захотим посетить $2$ (серую) вершину, то это будет означать, что мы отыскали цикл в этой вершине.

Осталось лишь вывести его на экран. Для этого ищем вершины, цвет которых $2$
(серый), так как нам достаточно вывести хотя бы один цикл, то для первой встретившейся вершины, в которой есть цикл, выведем вторую вершину.

Ссылки

Условие задачи на e-olymp

Код программы на ideone