Guest User

Untitled

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