Задача
Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них.
Входные данные
В первой строке находятся два натуральных числа $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 |
6 7 1 2 1 5 2 3 2 4 4 6 6 5 5 2 |
YES 2 4 6 5 |
| 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 3 4 2 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <iostream> #include <vector> using namespace std; vector<vector<int>> graph; vector<int> used, path; int flag, n, m; // поиск в глубину для каждой вершины void dfs (int v) { if (flag == 1) return; // если уже нашли цикл, то останавливаемся else { used[v] = 1; // посещаем вершину path.push_back(v); // добавляем ее в порядок обхода графа for (int i = 0; i < graph[v].size(); i++) { int to = graph[v][i];// следующая вершина графа if (used[to] == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл path.push_back(to); // добавляем следующую вершину в порядок обхода графа flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся return; } else { dfs(to); // если не посетили, то посещаем } if (flag == 1) return; // если нашли цикл, то останавливаемся } used[v] = 2; // если не нашли цикл, то выходим из вершины path.pop_back(); } } // проверяем вершины на наличие цикла void checkNodes() { for (int i = 1; i <= n; i++) { if (used[i] == 0) { // если не посещали вершину, то посещаем ее dfs(i); if (flag == 1) return; // если нашли цикл, то останавливаемся } } } int main(){ int v1, v2; cin >> n >> m; // считываем количество вершин и ребер graph.resize(n + 1); used.resize(n + 1, 0); for (int i = 0; i < m; i++) { cin >> v1 >> v2; // считываем ребра и заполняем граф graph[v1].push_back(v2); } checkNodes(); // проверяем вершины на наличие цикла if (flag == 1) { // если цикл найден int i = path.size() - 2; // последняя вершина цикла int to = path.back(); // вершина в которой зациклились while (path[i] != to) { // получаем индекс вершины в которой зациклились i--; } cout << "YES" << endl; while (i < path.size() - 1) { // выводим сам цикл cout << path[i] << " "; i++; } cout << endl; } else cout << "NO" << endl; } |
Решение
Для решения данной задачи воспользуемся поиском в глубину. Также будем отмечать вершины в различными цветами ($0$ (белый) — мы еще не посещали вершину, $1$ (серый) — посетили вершину и не вышли из нее (зациклились), $2$ (черный) — посетили вершину и вышли из неё).
В векторе $graph$ будем хранить сам граф, для проверки на цикличность воспользуемся вектором $visited$, так же будем хранить порядок обхода графа в векторе $path$. Так как по условию, в случае нескольких циклов, необходимо вывести любой, то мы будем находить первый и на этом останавливаться, для этого заведем переменную $flag$, которая равна 1, если цикл уже найден, и равна 0, если цикл еще не найден. В векторе $visited$ будем окрашивать вершину в один из цветов. Если мы захотим посетить $1$ (серую) вершину, то это будет означать, что мы отыскали цикл в этой вершине, тогда устанавливаем $flag = 1$.
Осталось лишь вывести его на экран. Для этого воспользуемся вектором $path$, в котором последний элемент — вершина, в которой цикл. Ищем предпоследнее вхождение этой вершины в векторе $path$ и выводим сам цикл.
Ссылки
Условие задачи на e-olymp
Код программы на ideone
Для отправки комментария необходимо войти на сайт.