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 n, m, fr, to;
- vector<vector <int>> g;
- vector<int> p;
- vector<int> clr;
- int cycle_end, cycle_st;
- bool cycle = false;
- void dfs(int v)
- {
- clr[v] = 1;
- for (int i = 0; i < g[v].size(); i++)
- {
- int a = g[v][i];
- if (clr[a] == 0)
- {
- clr[a] = 1;
- p[a] = v;
- dfs(a);
- }
- if (clr[a] == 1)
- {
- cycle_st = a;
- p[a] = v;
- cycle_end = v;
- cycle = true;
- break;
- }
- }
- clr[v] = 2;
- }
- int main()
- {
- ifstream in("cycle.in");
- ofstream out("cycle.out");
- in >> n >> m;
- g.resize(n);
- p.resize(n);
- clr.resize(n);
- for (int i = 0; i < m; i++)
- {
- in >> fr >> to;
- g[fr - 1].push_back(to - 1);
- }
- for (int i = 0; (i < n)&&(cycle == false); ++i)
- if (clr[i] == 0)
- dfs(i);
- if (cycle == false)
- out << "NO";
- else
- {
- out << "YES" << endl;
- vector<int> cycle_v;
- cycle_v.push_back (cycle_st);
- for (int v = cycle_end; v != cycle_st; v = p[v])
- cycle_v.push_back (v);
- reverse (cycle_v.begin(), cycle_v.end());
- for (size_t i = 0; i < cycle_v.size(); ++i)
- out << cycle_v[i] + 1 << " ";
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment