Advertisement
Georgiy031

Untitled

May 4th, 2020
355
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5. #include <cstdlib>
  6.  
  7. using namespace std;
  8.  
  9. void print(vector<int>& way) {
  10.     cout << "YES\n";
  11.     vector<int> ans;
  12.     for (int i = way.size() - 2; i >= 0; --i) {
  13.         ans.push_back(way[i] + 1);
  14.         if (way[i] == way.back()) break;
  15.     }
  16.     for (int i = ans.size() - 1; i >= 0; --i) {
  17.         cout << ans[i] << " ";
  18.     }
  19.     exit(0);
  20. }
  21. void dfs(int v, vector<int>& used, vector<set<int>>& g, vector<int>& way) {
  22.     used[v] = 1;
  23.     way.push_back(v);
  24.     for (auto to : g[v]) {
  25.         if (used[to] == 0) dfs(to, used, g, way);
  26.         else if (used[to] == 1) {
  27.             way.push_back(to);
  28.             print(way);
  29.         }
  30.     }
  31.     used[v] = 2;
  32.     way.pop_back();
  33. }
  34. int main() {
  35.     int n, m;
  36.     cin >> n >> m;
  37.     vector<set<int>> g(n);
  38.     vector<int> used(n, false);
  39.     vector<int> way;
  40.     for (int i = 0; i < m; ++i) {
  41.         int a, b;
  42.         cin >> a >> b;
  43.         --a, --b;
  44.         g[a].insert(b);
  45.     }
  46.     for (int i = 0; i < n; ++i) {
  47.         if (used[i] == 0) {
  48.             way.clear();
  49.             dfs(i, used, g, way);
  50.         }
  51.     }
  52.     cout << "NO";
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement