Advertisement
glcanvas

Untitled

Apr 25th, 2017
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <fstream>
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <iomanip>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <stack>
  9. #include <set>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <deque>
  14. #include <bitset>
  15. #include <tuple>
  16. //#include <math.h>
  17. #define ull int long long
  18. #define ll long long
  19. #define ld long double
  20. #define MAX 2e9
  21. #define MIN -2e9
  22. #define PI 3.14159265
  23. #define fst first
  24. #define scd second
  25. #define mp make_pair
  26. #define forn(i, x) for(int i = 0; i < x; i++)
  27. #define pb push_back
  28.  
  29. using namespace std;
  30. int n, m, s, t;
  31. vector< vector< int > > g;
  32. vector< int > color;
  33. int st = -1, ed = -1;
  34. vector< int> ans;
  35.  
  36. bool dfs(int v) {
  37.    color[v] = 1;
  38.    for(int i = 0; i < g[v].size(); i++) {
  39.       int to = g[v][i];
  40.       if(color[to] == 0) {
  41.          bool state =  dfs(to);
  42.          if(state) {
  43.                ans.pb(v);
  44.                return true;
  45.          }
  46.       } else if(color[to] == 1) {
  47.          st = v;
  48.          ans.pb(v);
  49.          return  true;
  50.       }
  51.    }
  52.    color[v] = 2;
  53.    return false;
  54.    }
  55.  
  56. int main() {
  57.  
  58.  //  freopen("cycle.in", "r", stdin);
  59.   // freopen("cycle.out", "w", stdout);
  60.    ios_base::sync_with_stdio(false);
  61.    cin.tie(NULL);
  62.    cin >> n >> m;
  63.    g.resize(n + 1);
  64.    color.resize(n + 1, 0);
  65.    for(int i = 0; i < m; i++) {
  66.       int a, b;
  67.       cin >> a>> b;
  68.       g[a].pb(b);
  69.    }
  70.    for(int i = 0; i <= n; i++) {
  71.       if(dfs(i)) {
  72.          cout << "YES\n";
  73.          reverse(ans.begin(), ans.end());
  74.          for(int j = 0; j < ans.size(); j++) {
  75.             cout << ans[j] << " ";
  76.          }
  77.          return 0;
  78.       }
  79.    }
  80.    cout << "NO";
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement