fork(1) download
copy 
  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
comments (?)
stdin
copy 
4 4
1 3
4 2
2 3
3 4
stdout
copy 
YES
3 4 2
https://ideone.com/uTHLaH
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!