Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. string fileName = "hamiltonian";
  10. ofstream out(fileName + ".out");
  11. ifstream in(fileName + ".in");
  12. int n, m;
  13. unsigned int MAX_N = 100 * 1000;
  14. vector<vector<int>> edges(MAX_N);
  15. vector<int> color(MAX_N, 0);
  16. vector<bool> was(MAX_N, false);
  17. vector<int> ans;
  18.  
  19. void input() {
  20.     in >> n >> m;
  21.     for (int i = 0; i < m; ++i) {
  22.         int x, y;
  23.         in >> x >> y;
  24.         edges[x - 1].push_back(y - 1);
  25.     }
  26. }
  27.  
  28. bool check() {
  29.     reverse(ans.begin(), ans.end());
  30.     for (int i = 0; i < ans.size() - 1; ++i) {
  31.         bool temp = false;
  32.         for (auto j: edges[ans[i]]) {
  33.             if (j == ans[i + 1]) temp = true;
  34.         }
  35.         if (!temp) return false;
  36.     }
  37.     return true;
  38. }
  39.  
  40.  
  41. void dfs(int v) {
  42.     was[v] = true;
  43.     for (auto to: edges[v]) {
  44.         if (!was[to])
  45.             dfs(to);
  46.     }
  47.     ans.push_back(v);
  48. }
  49.  
  50. void solve() {
  51.     for (int i = 0; i < n; ++i)
  52.         if (!was[i])
  53.             dfs(i);
  54.     if (check()) out << "YES";
  55.     else out << "NO";
  56.     //output();
  57. }
  58.  
  59.  
  60. bool cdfs(int v) {
  61.     color[v] = 1;
  62.     bool b = true;
  63.     for (auto i: edges[v]) {
  64.         if (color[i] == 0)
  65.             b = cdfs(i);
  66.         if (!b) return b;
  67.         if (color[i] == 1) return false;
  68.     }
  69.     color[v] = 2;
  70.     return b;
  71. }
  72.  
  73.  
  74. int main() {
  75.     input();
  76.     solve();
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement