Advertisement
ke_timofeeva7

с

Jan 11th, 2022
511
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. #include <cmath>
  5. #include <memory.h>
  6. #include <algorithm>
  7. #include <stack>
  8. #include <deque>
  9. #include <iomanip>
  10. #include <stdio.h>
  11. #include <queue>
  12. #include <chrono>
  13. #include <map>
  14. #include <set>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <random>
  18. #include <ctime>
  19. #include <cstdlib>
  20. #define int long long
  21. #define pii pair <int, int>
  22. #define pb push_back
  23. #define all(vc) vc.begin(), vc.end()
  24. #define fir first
  25. #define sec second
  26. #define endl "\n"
  27. #define un unsigned
  28. #define sp system("pause")
  29. #define INF 1000000009
  30. #define double long double
  31. using namespace std;
  32.  
  33. const int N = 500009, R = 1 << 20, nlog = 19, ABC = 26, MOD = 1e9 + 7;
  34.  
  35. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  36.  
  37. vector<pii> euler;
  38. vector<int> used;
  39.  
  40. void cycle(vector<vector<int>> &gr, int v, int p)
  41. {
  42.     used[v] = 1;
  43.  
  44.     for (auto u : gr[v])
  45.     {
  46.         if (!used[u])
  47.         {
  48.             cycle(gr, u, v);
  49.         }
  50.         else if (used[u] == 1)
  51.         {
  52.             cout << "No";
  53.             exit(0);
  54.         }
  55.     }
  56.  
  57.     used[v] = 2;
  58.     return;
  59. }
  60.  
  61. vector<int> dist;
  62.  
  63. vector<int> top_sort;
  64.  
  65. void ts(vector<vector<int>> &gr, int v)
  66. {
  67.     used[v] = 1;
  68.  
  69.     for (auto u : gr[v])
  70.     {
  71.         if (!used[u])
  72.         {
  73.             ts(gr, u);
  74.         }
  75.     }
  76.  
  77.     top_sort.push_back(v);
  78. }
  79.  
  80. int cur = 1;
  81.  
  82. vector<int> ans;
  83.  
  84. void dfs(vector<vector<int>> &gr, int v, int p)
  85. {
  86.     used[v] = 1;
  87.     euler[v].first = cur;
  88.     cur++;
  89.  
  90.     for (auto u : gr[v])
  91.     {
  92.         if (!used[u] && dist[u] == dist[v] + 1)
  93.         {
  94.             ans[u] = v;
  95.             dfs(gr, u, p);
  96.         }
  97.         else if (used[u])
  98.         {
  99.             if (euler[v].first > euler[u].first)
  100.             {
  101.                 cout << "No";
  102.                 exit(0);
  103.             }
  104.         }
  105.     }
  106.  
  107.     euler[v].second = cur;
  108.     cur++;
  109.     return;
  110. }
  111.  
  112. signed main()
  113. {
  114.     ios_base::sync_with_stdio(false);
  115.     cin.tie(0);
  116.     cout.tie(0);
  117.  
  118.     int n, m;
  119.     cin >> n >> m;
  120.  
  121.     euler.assign(n + 1, { 0, 0 });
  122.     ans.assign(n + 1, -1);
  123.  
  124.     vector<vector<int>> gr(n + 1);
  125.  
  126.     vector<int> st(n + 1, 0);
  127.  
  128.     for (int i = 0; i < m; i++)
  129.     {
  130.         int a, b;
  131.         cin >> a >> b;
  132.  
  133.         gr[a].pb(b);
  134.         st[b]++;
  135.     }
  136.  
  137.     for (int i = 1; i <= n; i++)
  138.     {
  139.         sort(all(gr[i]));
  140.         gr[i].erase(unique(all(gr[i])), gr[i].end());
  141.     }
  142.  
  143.     int cnt = 0, start = 0;
  144.  
  145.     for (int i = 1; i <= n; i++)
  146.     {
  147.         if (st[i] == 0)
  148.         {
  149.             cnt++;
  150.             start = i;
  151.         }
  152.     }
  153.  
  154.     if (cnt != 1)
  155.     {
  156.         cout << "No";
  157.         exit(0);
  158.     }
  159.  
  160.     used.assign(n + 1, 0);
  161.  
  162.     cycle(gr, start, -1);
  163.  
  164.     for (int i = 1; i <= n; i++)
  165.     {
  166.         if (!used[i])
  167.         {
  168.             cout << "No";
  169.             exit(0);
  170.         }
  171.     }
  172.  
  173.     used.assign(n + 1, 0);
  174.  
  175.     ts(gr, start);
  176.  
  177.     reverse(all(top_sort));
  178.  
  179.     dist.assign(n + 1, 0);
  180.  
  181.     dist[start] = 1;
  182.  
  183.     for (auto i : top_sort)
  184.     {
  185.         for (auto u : gr[i])
  186.         {
  187.             dist[u] = max(dist[u], dist[i] + 1);
  188.         }
  189.     }
  190.  
  191.     used.assign(n + 1, 0);
  192.  
  193.     dfs(gr, start, -1);
  194.  
  195.     cout << "Yes" << endl;
  196.  
  197.     for (int i = 1; i <= n; i++)
  198.     {
  199.         cout << ans[i] << " ";
  200.     }
  201.  
  202.     //sp;
  203.     return 0;
  204. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement