Guest User

Untitled

a guest
Jan 19th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #pragma comment (linker, "/STACK:64000000")
  4.  
  5. using namespace std;
  6.  
  7. int n, m, fr, to;
  8. vector<vector <int>> g;
  9. vector<int> p;
  10. vector<int> clr;
  11. int cycle_end, cycle_st;
  12. bool cycle = false;
  13.  
  14. void dfs(int v)
  15. {
  16.     clr[v] = 1;
  17.     for (int i = 0; i <  g[v].size(); i++)
  18.     {
  19.         int a = g[v][i];
  20.         if (clr[a] == 0)
  21.         {
  22.             clr[a] = 1;
  23.             p[a] = v;
  24.             dfs(a);
  25.         }
  26.         if (clr[a] == 1)
  27.         {
  28.             cycle_st = a;
  29.             p[a] = v;
  30.             cycle_end = v;
  31.             cycle = true;
  32.             break;
  33.         }
  34.     }
  35.     clr[v] = 2;
  36. }
  37.  
  38. int main()
  39. {
  40.     ifstream in("cycle.in");
  41.     ofstream out("cycle.out");
  42.  
  43.     in >> n >> m;
  44.  
  45.     g.resize(n);
  46.     p.resize(n);
  47.     clr.resize(n);
  48.     for (int i = 0; i < m; i++)
  49.     {
  50.         in >> fr >> to;
  51.         g[fr - 1].push_back(to - 1);
  52.     }
  53.  
  54.     for (int i = 0; (i < n)&&(cycle == false); ++i)
  55.         if (clr[i] == 0)
  56.             dfs(i);
  57.  
  58.     if (cycle == false)
  59.         out << "NO";
  60.     else
  61.     {
  62.         out << "YES" << endl;
  63.         vector<int> cycle_v;
  64.         cycle_v.push_back (cycle_st);
  65.         for (int v = cycle_end; v != cycle_st; v = p[v])
  66.             cycle_v.push_back (v);
  67.  
  68.         reverse (cycle_v.begin(), cycle_v.end());
  69.         for (size_t i = 0; i < cycle_v.size(); ++i)
  70.             out << cycle_v[i] + 1 << " ";
  71.  
  72.     }
  73.     return 0;
  74. }
Add Comment
Please, Sign In to add comment