Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #pragma comment (linker, "/STACK:64000000")
- using namespace std;
- int m, n, fr, to;
- vector <vector <int>> g;
- vector <int> clr;
- vector <int> tmp;
- bool cycle = false;
- void dfs (int v)
- {
- clr[v] = 1;
- for (size_t i = 0; i < g[v].size(); ++i)
- {
- int a = g[v][i];
- if (clr[a] == 0)
- {
- clr[a] = 1;
- dfs(a);
- }
- if (clr[a] == 1)
- cycle = true;
- }
- tmp.push_back(v);
- clr[v] = 2;
- }
- void topological_sort()
- {
- for (int i = 0; (i < n)&&(cycle == false); i++)
- if (clr[i] == 0)
- dfs(i);
- reverse(tmp.begin(), tmp.end());
- }
- bool is_gam()
- {
- bool res = false;
- for(int i = 0; i < n - 1; i++)
- {
- int a = tmp[i];
- int b = tmp[i + 1];
- for(int j = 0; j < g[a].size(); j++)
- {
- if(g[a][j] == b)
- res = true;
- }
- if(!res)
- return false;
- res = false;
- }
- return true;
- }
- int main()
- {
- ifstream in("hamiltonian.in");
- ofstream out("hamiltonian.out");
- in >> n >> m;
- g.resize(n);
- clr.resize(n);
- for (int i = 0; i < m; i++)
- {
- in >> fr >> to;
- g[fr - 1].push_back(to - 1);
- }
- topological_sort();
- if (is_gam() == true)
- out << "YES";
- else
- out << "NO";
- return 0;
- }
Add Comment
Please, Sign In to add comment