fork download
  1. import java.util.*;
  2.  
  3. enum Color {
  4. WHITE, GRAY, BLACK; // Вводим тип данных, отвечающий за цвет вершины
  5. }
  6.  
  7. class Main {
  8. static final List<Color> color = new ArrayList<>(); // Список, в котором указаны цвета всех вершин
  9. static final List<List<Integer>> crossroads = new ArrayList<>(); // Списки смежности перекрестков
  10.  
  11. public static void main(String[] args) {
  12. int n, m; // Количество перекрестков и дорог
  13. Scanner in = new Scanner(System.in);
  14. n = in.nextInt();
  15. m = in.nextInt();
  16. for (int i = 0; i < n; i++) {
  17. color.add(Color.WHITE); // Окрашиваем все вершины в белый цвет
  18. }
  19. for (int i = 0; i < n; i++) {
  20. crossroads.add(new LinkedList<Integer>());
  21. }
  22. for (int i = 0; i < m; i++) {
  23. int u, v; // Номер перекрестков, соединенных дорогой
  24. u = in.nextInt();
  25. v = in.nextInt();
  26. u--;v--; // Так как по условию отсчёт начинается с первой вершины, вычитаем 1 для удобства
  27. boolean isAlreadyRoad = false; // Проверяем, не повторяется ли дорога
  28. List<Integer> uNeighbours = crossroads.get(u);
  29. List<Integer> vNeighbours = crossroads.get(v);
  30. if (!uNeighbours.isEmpty() && !vNeighbours.isEmpty()) {
  31. if (uNeighbours.contains(v)) isAlreadyRoad = true;
  32. }
  33. if (!isAlreadyRoad) { // Проверка на повторение
  34. uNeighbours.add(v); // Добавляем в список доступных перекрестков перекрестка u перекресток v
  35. vNeighbours.add(u); // Аналогичные действия для перекрестка v, чтобы учесть возможность двусторонней езды
  36. }
  37. }
  38. System.out.print(isTrack(0, 0) ? "YES" : "NO"); // Запускаем метод, что ищет круговую трассу с первого перекрестка и выводим ответ
  39. }
  40.  
  41. public static boolean isTrack(int crossroad, int parent) { // Метод, проверяющий наличие круговой трассы
  42. if (color.get(crossroad) == Color.GRAY) return true; // Условие существования цикла
  43. color.set(crossroad, Color.GRAY);
  44. List<Integer> crossroadNeighbours = crossroads.get(crossroad);
  45. for (Integer nextCrossroad : crossroadNeighbours) { // Переход в соседние вершины
  46. if (parent != nextCrossroad && isTrack(nextCrossroad, crossroad)) return true; // Вход в вершину, в которую еще не входили
  47. }
  48. color.set(crossroad, Color.BLACK); // Если дальше нет цикла, окрашиваем вершину в черный
  49. return false;
  50. }
  51. }
Success #stdin #stdout 0.1s 35524KB
stdin
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
stdout
YES