Задача
В городе $N$ в ближайшее время состоится этап чемпионата мира по автогонкам среди автомобилей класса Формула-0. Поскольку специальный автодром для этих соревнований организаторы построить не успели, было решено организовать трассу на улицах города.
В городе $N$ есть $n$ перекрёстков, некоторые пары которых соединены дорогами, движение по которым возможно в обоих направлениях. При этом любые два перекрёстка соединены не более чем одной дорогой, и есть возможность доехать по дорогам от любого перекрёстка до любого другого.
Трасса, на которой будут проводится соревнования, должна быть круговой (т.е. должна начинаться и заканчиваться на одном и том же перекрёстке), при этом в процессе движения по ней никакой перекрёсток не должен встречаться более одного раза.
На предварительном этапе подготовки оргкомитетом был создан список всех дорог города. Теперь настало время его использовать. Первый вопрос, который необходимо решить, — это вопрос о существовании в городе требуемой круговой трассы (разумеется, если ответ будет отрицательным, организаторам придётся в срочном порядке построить ещё несколько дорог). Единственная проблема заключается в том, что у организаторов есть подозрение, что, поскольку список составлялся не очень внимательно, в нём некоторые дороги указаны более одного раза.
Напишите программу, которая по заданному списку дорог города определит, возможна ли организация в городе требуемой круговой трассы.
Входные данные
Первая строка содержит два целых числа: количество перекрёстков $n$ $(1 \leqslant n \leqslant 1000)$ в городе $N$ и количество дорог $m$ $(0 \leqslant m \leqslant 100000)$ в составленном списке.
Последующие $m$ строк описывают дороги. Каждая дорога описывается двумя числами: $u$ и $v$ $(1 \leqslant u, v \leqslant n, u ≠ v)$ — номера перекрёстков, которые она соединяет. Так как дороги двусторонние, то пара чисел $(u, v)$ и пара чисел $(v, u)$ описывают одну и ту же дорогу.
Выходные данные
Вывести YES, если в городе возможно организовать круговую трассу для соревнований, и слово NO в противном случае.
Тесты
| Входные данные | Выходные данные |
| 3 4 1 2 2 3 3 1 3 2 |
YES |
| 2 3 1 2 2 1 2 1 |
NO |
| 8 10 1 4 4 7 7 8 5 6 1 5 6 7 4 1 4 3 2 3 1 5 |
YES |
| 6 5 4 2 1 2 2 3 2 5 5 6 |
NO |
| 8 8 1 5 1 6 4 7 8 4 1 3 2 1 4 1 5 6 |
YES |
| 8 12 8 5 4 3 4 6 4 1 2 4 2 3 4 3 5 1 5 7 7 6 4 2 1 2 |
YES |
Код программы
|
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 |
import java.util.*; enum Color { WHITE, GRAY, BLACK; // Вводим тип данных, отвечающий за цвет вершины } class Main { static final List<Color> color = new ArrayList<>(); // Список, в котором указаны цвета всех вершин static final List<List<Integer>> crossroads = new ArrayList<>(); // Списки смежности перекрестков public static void main(String[] args) { int n, m; // Количество перекрестков и дорог Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); for (int i = 0; i < n; i++) { color.add(Color.WHITE); // Окрашиваем все вершины в белый цвет } for (int i = 0; i < n; i++) { crossroads.add(new LinkedList<Integer>()); } for (int i = 0; i < m; i++) { int u, v; // Номер перекрестков, соединенных дорогой u = in.nextInt(); v = in.nextInt(); u--;v--; // Так как по условию отсчёт начинается с первой вершины, вычитаем 1 для удобства boolean isAlreadyRoad = false; // Проверяем, не повторяется ли дорога List<Integer> uNeighbours = crossroads.get(u); List<Integer> vNeighbours = crossroads.get(v); if (!uNeighbours.isEmpty() && !vNeighbours.isEmpty()) { if (uNeighbours.contains(v)) isAlreadyRoad = true; } if (!isAlreadyRoad) { // Проверка на повторение uNeighbours.add(v); // Добавляем в список доступных перекрестков перекрестка u перекресток v vNeighbours.add(u); // Аналогичные действия для перекрестка v, чтобы учесть возможность двусторонней езды } } System.out.print(isTrack(0, 0) ? "YES" : "NO"); // Запускаем метод, что ищет круговую трассу с первого перекрестка и выводим ответ } public static boolean isTrack(int crossroad, int parent) { // Метод, проверяющий наличие круговой трассы if (color.get(crossroad) == Color.GRAY) return true; // Условие существования цикла color.set(crossroad, Color.GRAY); List<Integer> crossroadNeighbours = crossroads.get(crossroad); for (Integer nextCrossroad : crossroadNeighbours) { // Переход в соседние вершины if (parent != nextCrossroad && isTrack(nextCrossroad, crossroad)) return true; // Вход в вершину, в которую еще не входили } color.set(crossroad, Color.BLACK); // Если дальше нет цикла, окрашиваем вершину в черный return false; } } |
Объяснение
По условию ясно, что нам необходимо создать неориентированный граф с $n$ вершинами. Ребрами в созданном графе являются дороги, соединяющие по два перекрестка каждая. Сам граф можно записать с помощью списков смежности. Во входных данных может быть записана одна и та же дорога по несколько раз. Это никак не скажется на результате программы, но будет использовано больше памяти в сравнении с тем вариантом, если их проигнорировать. Достаточно проверить в списке первой вершины наличие второй, чтобы не учитывать повторения.
Круговая трасса в городе представляет в структуре графа представляется циклом. Для его поиска можно использовать обход в глубину (DFS). Обход можно начинать с любой вершины, ведь от этого результат не зависит. Для определенности в коде, указанном выше, обход начинается с нулевой (в самой задаче с первой). Для вершин также введем дополнительную характеристику. Назовем не посещенную вершину белой (WHITE), посещенную — серой (GRAY). Вершину, из которой более некуда идти, обозначим черной (BLACK). Также вершину, из которой мы пришли, назовем родителем. При заходе в граф каждая вершина является белой. При входе в вершину мы проверяем, не является ли она серой. Если да, то это означает, что мы нашли цикл, и можем заканчивать обход и выводить YES. Если вершина является белой, то она окрашивается в серый. Далее из нее идет переход в доступную вершину из данной, кроме родителя. В следующей вершине повторяются все прошлые действия. Если из вершины больше нельзя никуда пойти, кроме как назад, то она становится черной и совершается возврат в родителя. И, наконец, если все вершины — черные, то цикла нет. Значит можно заканчивать обход и выводить NO.