Advertisement
Guest User

Untitled

a guest
Nov 18th, 2019
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> gr[100005];
  8. char cl[100005];
  9. int pr[100005];
  10.  
  11. int cyc_st = -1;
  12. int cyc_end = -1;
  13.  
  14. bool dfs(int v, int p) {
  15.     cl[v] = 1;
  16.     pr[v] = p;
  17.     for (auto it : gr[v]) {
  18.         if (cl[it] == 1) {
  19.             cyc_st = it;
  20.             cyc_end = v;
  21.             return true;
  22.         }
  23.         else if (cl[it] == 0) {
  24.             return dfs(it, v);
  25.         }
  26.     }
  27.     cl[v] = 2;
  28.     return false;
  29. }
  30.  
  31. int main() {
  32.     int n, m;
  33.     cin >> n >> m;
  34.     for (int i = 0; i < m; i++) {
  35.         int u, v;
  36.         cin >> u >> v;
  37.         gr[u].push_back(v);
  38.     }
  39.     for (int i = 1; i <= n; i++) {
  40.         if (cl[i] == 0) {
  41.             if (dfs(i, -1)) break;
  42.         }
  43.     }
  44.     if (cyc_st == -1) {
  45.         cout << "NO\n";
  46.     }
  47.     else {
  48.         cout << "YES\n";
  49.         vector<int> cycle;
  50.         for (int i = cyc_end; i != cyc_st; i = pr[i]) {
  51.             cycle.push_back(i);
  52.         }
  53.         cycle.push_back(cyc_st);
  54.         reverse(cycle.begin(), cycle.end());
  55.         for (auto it : cycle) {
  56.             cout << it << " ";
  57.         }
  58.     }
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement