Задача
Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них.
Входные данные
В первой строке находятся два натуральных числа $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 63 64 65 66 67 68 |
import java.util.*; public class Main { public static int n, m, flag = 0; public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>(); public static ArrayList<Integer> used = new ArrayList<Integer>(); public static ArrayList<Integer> path = new ArrayList<Integer>(); // поиск в глубину для каждой вершины static void dfs(int v) { if (flag == 1) return; // если уже нашли цикл, то останавливаемся else { used.set(v, 1); // посещаем вершину path.add(v); // добавляем ее в порядок обхода графа for (int i = 0; i < graph.get(v).size(); i++) { int to = graph.get(v).get(i); // следующая вершина графа if (used.get(to) == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл path.add(to); // добавляем следующую вершину в порядок обхода графа flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся return; } else dfs(to); // если не посетили, то посещаем if (flag == 1) return; // если нашли цикл, то останавливаемся } used.set(v, 2); // если не нашли цикл, то выходим из вершины path.remove(path.size() - 1); } } // проверяем вершины на наличие цикла static void checkNodes() { for (int i = 0; i <= n; i++) { if (used.get(i) == 0) { // если не посещали вершину, то посещаем ее dfs(i); if (flag == 1) return; // если нашли цикл, то останавливаемся } } } public static void main (String[] args) { Scanner s = new Scanner(System.in); // считываем количество вершин и ребер n = s.nextInt(); m = s.nextInt(); for (int i = 0; i <= n; i++) { used.add(0); graph.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { // считываем ребра и заполняем граф int v1 = s.nextInt(); int v2 = s.nextInt(); graph.get(v1).add(v2); } checkNodes(); // проверяем вершины на наличие цикла if (flag == 1) { // если цикл найден int i = path.size() - 2; // последняя вершина цикла int to = path.get(path.size() - 1); // вершина в которой зациклились while (path.get(i) != to) { // получаем индекс вершины в которой зациклились i--; } System.out.println("YES"); while (i < path.size() - 1) { // выводим сам цикл System.out.print(path.get(i) + " "); i++; } System.out.println(); } else System.out.print("NO"); } } |
Решение
Для решения данной задачи воспользуемся поиском в глубину. Также будем отмечать вершины в различными цветами ($0$ (белый) — мы еще не посещали вершину, $1$ (серый) — посетили вершину и не вышли из нее (зациклились), $2$ (черный) — посетили вершину и вышли из неё).
В векторе $graph$ будем хранить сам граф, для проверки на цикличность воспользуемся вектором $visited$, так же будем хранить порядок обхода графа в векторе $path$. Так как по условию, в случае нескольких циклов, необходимо вывести любой, то мы будем находить первый и на этом останавливаться, для этого заведем переменную $flag$, которая равна 1, если цикл уже найден, и равна 0, если цикл еще не найден. В векторе $visited$ будем окрашивать вершину в один из цветов. Если мы захотим посетить $1$ (серую) вершину, то это будет означать, что мы отыскали цикл в этой вершине, тогда устанавливаем $flag = 1$.
Осталось лишь вывести его на экран. Для этого воспользуемся вектором $path$, в котором последний элемент — вершина, в которой цикл. Ищем предпоследнее вхождение этой вершины в векторе $path$ и выводим сам цикл.
Ссылки
Условие задачи на e-olymp
Код программы на ideone