fork download
  1. import java.util.*;
  2. public class Main {
  3. public static int n, m, flag = 0;
  4. public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
  5. public static ArrayList<Integer> used = new ArrayList<Integer>();
  6. public static ArrayList<Integer> path = new ArrayList<Integer>();
  7. // поиск в глубину для каждой вершины
  8. static void dfs(int v) {
  9. if (flag == 1) return; // если уже нашли цикл, то останавливаемся
  10. else {
  11. used.set(v, 1); // посещаем вершину
  12. path.add(v); // добавляем ее в порядок обхода графа
  13. for (int i = 0; i < graph.get(v).size(); i++) {
  14. int to = graph.get(v).get(i); // следующая вершина графа
  15. if (used.get(to) == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл
  16. path.add(to); // добавляем следующую вершину в порядок обхода графа
  17. flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся
  18. return;
  19. }
  20. else dfs(to); // если не посетили, то посещаем
  21. if (flag == 1) return; // если нашли цикл, то останавливаемся
  22. }
  23. used.set(v, 2); // если не нашли цикл, то выходим из вершины
  24. path.remove(path.size() - 1);
  25. }
  26. }
  27. // проверяем вершины на наличие цикла
  28. static void checkNodes() {
  29. for (int i = 0; i <= n; i++) {
  30. if (used.get(i) == 0) { // если не посещали вершину, то посещаем ее
  31. dfs(i);
  32. if (flag == 1) return; // если нашли цикл, то останавливаемся
  33. }
  34. }
  35. }
  36. public static void main (String[] args) {
  37. Scanner s = new Scanner(System.in);
  38. // считываем количество вершин и ребер
  39. n = s.nextInt();
  40. m = s.nextInt();
  41. for(int i = 0; i <= n; i++) {
  42. used.add(0);
  43. graph.add(new ArrayList<>());
  44. }
  45. for(int i = 0; i < m; i++) {
  46. // считываем ребра и заполняем граф
  47. int v1 = s.nextInt();
  48. int v2 = s.nextInt();
  49. graph.get(v1).add(v2);
  50. }
  51. checkNodes(); // проверяем вершины на наличие цикла
  52. if (flag == 1) { // если цикл найден
  53. int i = path.size() - 2; // последняя вершина цикла
  54. int to = path.get(path.size() - 1); // вершина в которой зациклились
  55. while (path.get(i) != to) { // получаем индекс вершины в которой зациклились
  56. i--;
  57. }
  58. System.out.println("YES");
  59. while (i < path.size() - 1) { // выводим сам цикл
  60. System.out.print(path.get(i) + " ");
  61. i++;
  62. }
  63. System.out.println();
  64. }
  65. else
  66. System.out.print("NO");
  67. }
  68. }
  69.  
Success #stdin #stdout 0.2s 37620KB
stdin
6 7
1 2
1 5
2 3
2 4
4 6
6 5
5 2
stdout
YES
2 4 6 5