Georgiy031

Untitled

May 4th, 2020
359
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int n, m;
  6. vector <vector <int> > graf;
  7. vector <int> colours;
  8. vector <int> cycle;
  9.  
  10. bool dfs(int v) {
  11.     colours[v] = 2;
  12.     for (int i = 0; i < graf[v].size(); i++) {
  13.         if (colours[graf[v][i]] == 1) {
  14.             if (dfs(graf[v][i])) {
  15.                 cycle.push_back(v);
  16.                 return true;
  17.             }
  18.         }
  19.         else if (colours[graf[v][i]] == 2) {
  20.             cycle.push_back(graf[v][i]);
  21.             cycle.push_back(v);
  22.             return true;
  23.         }
  24.     }
  25.     colours[v] = 3;
  26.     return false;
  27. }
  28.  
  29. int main() {
  30.     cin >> n >> m;
  31.     graf.resize(n);
  32.     int v1, v2;
  33.     colours.resize(n, 1);
  34.     for (int i = 0; i < m; i++) {
  35.         cin >> v1 >> v2;
  36.         graf[v1 - 1].push_back(v2 - 1);
  37.     }
  38.  
  39.     for (int i = 0; i < n; i++) {
  40.         if (colours[i] == 1 && dfs(i)) {
  41.  
  42.             cout << "YES\n";
  43.             bool find = false;
  44.             for (int i = cycle.size() - 1; i >= 0; --i) {
  45.                 if(find) cout << cycle[i] + 1 << " ";
  46.                 if (find == false && cycle[i] == cycle[0]) find = true;
  47.             }
  48.  
  49.             return 0;
  50.         }
  51.     }
  52.     cout << "NO";
  53. }
Advertisement
Add Comment
Please, Sign In to add comment