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