Raslboyy

166

Nov 7th, 2019
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include <iostream>
  2. //#include <chrono>
  3. //#include <fstream>
  4. //#include <bits/stdc++.h>
  5. #include <vector>
  6. #include <list>
  7. #include <algorithm>
  8.  
  9. #define mp make_pair
  10. #define pb push_back
  11. #define eb emplace_back
  12. #define f first
  13. #define s second
  14. #define sz(x) (int)x.size()
  15. #define all(x) begin(x), end(x)
  16. #define rall(x) rbegin(x), rend(x)
  17.  
  18. using namespace std;
  19.  
  20. typedef unsigned long long ull;
  21. typedef long long ll;
  22. typedef long double ld;
  23. typedef pair<int, int> pi;
  24. typedef pair<ll, ll> pl;
  25.  
  26. vector<list<int>> vec;
  27. vector<char> color;
  28. vector<int> answ;
  29.  
  30. bool dfs(int v) {
  31.     color[v] = 1;
  32.     int count_b = 0;
  33.     int count = 0;
  34.     for (int i : vec[v]) {
  35.         if (color[i] == 0) {
  36.             dfs(i);
  37.         }
  38.         else if (color[i] == 1) {
  39.             cout << "No\n";
  40.             exit(0);
  41.         }
  42.     }
  43.     color[v] = 2;
  44.     answ.pb(v + 1);
  45.     return count == count_b;
  46. }
  47.  
  48. int main() {
  49.     /*ifstream cin("in.txt");
  50.     ofstream cout("out.txt");
  51.     auto start_time = chrono::high_resolution_clock::now();*/
  52.  
  53.     ios::sync_with_stdio(false);
  54.     cin.tie(0);
  55.     cout.tie(0);
  56.  
  57.     int n, m;
  58.     cin >> n >> m;
  59.     vec.assign(n, list<int>());
  60.     color.assign(n, 0);
  61.     for (int i = 0; i < m; i++) {
  62.         int a, b;
  63.         cin >> a >> b;
  64.         vec[--a].eb(--b);
  65.     }
  66.     answ.reserve(n);
  67.     for (int i = 0; i < n; i++) {
  68.         if (!color[i]) {
  69.             if (!dfs(i)) {
  70.                 cout << "No" << endl;
  71.                 return 0;
  72.             }
  73.         }
  74.     }
  75.     cout << "Yes" << endl;
  76.     reverse(all(answ));
  77.     for (int i : answ)
  78.         cout << i << " ";
  79.  
  80.     /*auto end_time = chrono::high_resolution_clock::now();
  81.     chrono::duration<double> duration = end_time - start_time;
  82.     cout << duration.count() << "\n";
  83.     cin.close();
  84.     cout.close();*/
  85.     return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment