Advertisement
Guest User

Untitled

a guest
Oct 20th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. class Graph {
  10. private:
  11.     vector<vector<int> > graph;
  12.     int vertex;
  13.  
  14. public:
  15.     Graph(vector<vector<int> > graph) : graph(graph) {
  16.         vertex = graph.size();
  17.     }
  18.    
  19.     bool dfs(int index, vector<int>& color, vector<int>& parent, int &_end, int &_start) {
  20.         color[index] = 1;
  21.        
  22.         for (unsigned int i = 0; i < graph[index].size(); ++i) {
  23.             int to = graph[index][i];
  24.            
  25.             if (color[to] == 0) {
  26.                 parent[to] = index;
  27.                 if (dfs(to, color, parent, _end, _start))  return true; //цикл нашелся
  28.             }
  29.            
  30.             else if (color[to] == 1) {
  31.                 _end = index;
  32.                 _start = to;
  33.                 return true;
  34.             }
  35.         }
  36.        
  37.         color[index] = 2;
  38.         return false;
  39.     }
  40.    
  41.     bool find_cycle(vector <int> &cycle) {
  42.         vector<int> color(vertex, 0);
  43.         vector<int> parent(vertex, -1);
  44.         int _start, _end;
  45.         _start = -1;
  46.         for (int i = 0; i < vertex; ++i)
  47.             if(!color[i])
  48.                 if (dfs(i, color, parent, _end, _start))
  49.                     break;
  50.         if (_start == -1)
  51.             return false;
  52.         else {
  53.             cycle.push_back(_start);
  54.             for (int index = _end; index != _start; index = parent[index])
  55.                 cycle.push_back(index);
  56.             reverse(cycle.begin(), cycle.end());
  57.             return true;
  58.         }
  59.  
  60.     }
  61. };
  62.  
  63.  
  64. int main()
  65. {
  66.     int vertex, edges;
  67.     cin >> vertex >> edges;
  68.     vector<vector<int> > matrix(vertex);
  69.    
  70.     for (int i = 0; i < edges; i++) {
  71.         int to, from;
  72.         cin >> from >> to;
  73.         matrix[from - 1].push_back(to - 1);
  74.     }
  75.    
  76.     Graph graph(matrix);
  77.     vector <int> cycle;
  78.    
  79.     if (!graph.find_cycle(cycle)) {
  80.         cout << "NO" << endl;
  81.     } else {
  82.         cout << "YES" << endl;
  83.         for (unsigned int i = 0; i < cycle.size(); ++i)
  84.             cout << cycle[i] + 1 << " ";
  85.     }
  86.    
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement