Advertisement
achulkov2

Untitled

Apr 15th, 2018
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.33 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. #include <string>
  4.  
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. vector<vector<int>> graph;
  10. vector<int> color;
  11. vector<int> vertexes;
  12.  
  13. void printCycle(int ver) {
  14. int counter = 0;
  15. for (int i = vertexes.size() - 1; i >= 0 && vertexes[i] != ver; i--) {
  16. counter++;
  17. }
  18. cout << counter + 1 << "\n";
  19. for (int i = vertexes.size() - 1; i >= 0 && vertexes[i] != ver; i--) {
  20. cout << vertexes[i] + 1 << " ";
  21. }
  22. cout << ver + 1 << "\n";
  23. exit(0);
  24. }
  25.  
  26. void dfs(int v, int from) {
  27. color[v] = 1;
  28. vertexes.push_back(v);
  29. for (int i = 0; i < (int)graph[v].size(); i++) {
  30. int vertex = graph[v][i];
  31. if (color[vertex] == 0)
  32. dfs(vertex, v);
  33. if (color[vertex] == 1 && vertex != from) {
  34. cout << "YES\n";
  35. printCycle(vertex);
  36. }
  37. }
  38. vertexes.pop_back();
  39. color[v] = 2;
  40. }
  41.  
  42. int main() {
  43. int n;
  44. cin >> n;
  45. graph.resize(n, vector<int>());
  46. color.resize(n);
  47. for (int i = 0; i < n; i++) {
  48. for (int j = 0; j < n; j++) {
  49. int a;
  50. cin >> a;
  51. if (a == 1)
  52. graph[i].push_back(j);
  53. }
  54. }
  55.  
  56. for (int i = 0; i < n; i++) {
  57. if (color[i] == 0)
  58. dfs(i, -1);
  59. }
  60.  
  61. cout << "NO";
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement