Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- vector<int> gr[100005];
- char cl[100005];
- int pr[100005];
- int cyc_st = -1;
- int cyc_end = -1;
- bool dfs(int v, int p) {
- cl[v] = 1;
- pr[v] = p;
- for (auto it : gr[v]) {
- if (cl[it] == 1) {
- cyc_st = it;
- cyc_end = v;
- return true;
- }
- else if (cl[it] == 0) {
- return dfs(it, v);
- }
- }
- cl[v] = 2;
- return false;
- }
- int main() {
- int n, m;
- cin >> n >> m;
- for (int i = 0; i < m; i++) {
- int u, v;
- cin >> u >> v;
- gr[u].push_back(v);
- }
- for (int i = 1; i <= n; i++) {
- if (cl[i] == 0) {
- if (dfs(i, -1)) break;
- }
- }
- if (cyc_st == -1) {
- cout << "NO\n";
- }
- else {
- cout << "YES\n";
- vector<int> cycle;
- for (int i = cyc_end; i != cyc_st; i = pr[i]) {
- cycle.push_back(i);
- }
- cycle.push_back(cyc_st);
- reverse(cycle.begin(), cycle.end());
- for (auto it : cycle) {
- cout << it << " ";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement