Advertisement
makinotori14

Untitled

Dec 14th, 2023
914
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.78 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ld = long double;
  7. using ull = unsigned long long;
  8. using pii = pair<int, int>;
  9.  
  10. mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  11.  
  12. template <typename T1, typename T2>
  13. ostream& operator <<(ostream& out, pair<T1, T2> &p) {
  14.     out << '{' << p.first << ", " << p.second << '}';
  15.     return out;
  16. }
  17.  
  18. template <typename T>
  19. ostream& operator <<(ostream& out, set<T> &s) {
  20.     for (auto &x : s)
  21.         out << x << ' ';
  22.     return out;
  23. }
  24.  
  25. template <typename T>
  26. ostream& operator <<(ostream &out, multiset<T> &s) {
  27.     for (auto &x : s)
  28.         out << x << ' ';
  29.     return out;
  30. }
  31.  
  32. template <typename T>
  33. bool ckmin(T &a, T b) {
  34.     return (a > b ? a = b, true : false);
  35. }
  36.  
  37. template <typename T>
  38. bool ckmax(T &a, T b) {
  39.     return (a < b ? a = b, true : false);
  40. }
  41.  
  42. template <typename T>
  43. ostream& operator <<(ostream& out, vector<T> &v) {
  44.     for (auto &x : v)
  45.         cout << x << ' ';
  46.     return out;
  47. }
  48.  
  49. void visit(vector<vector<int>> &g, vector<char> &vis, int v) {
  50.     vis[v] = 1;
  51.     for (auto &u : g[v]) {
  52.         if (!vis[u])
  53.             visit(g, vis, u);
  54.     }
  55. }
  56.  
  57. bool check_comp(vector<vector<int>> &g) {
  58.     vector<vector<int>> g_unor((int)g.size());
  59.     for (int v = 0; v < (int)g.size(); ++v) {
  60.         for (auto &u : g[v]) {
  61.             g_unor[v].push_back(u);
  62.             g_unor[u].push_back(v);
  63.         }
  64.     }
  65.  
  66.     vector<char> vis((int)g.size());
  67.     visit(g_unor, vis, 0);
  68.  
  69.     return count(vis.begin(), vis.end(), 1) == (int)g.size();
  70. }
  71.  
  72. bool ts_dfs(vector<vector<int>> &g, vector<char> &vis, int v, vector<int> &ts) {
  73.     vis[v] = 1;
  74.     for (auto &u : g[v]) {
  75.         if (vis[u] == 1) {
  76.             return false;
  77.         }
  78.         if (!vis[u]) {
  79.             if (!ts_dfs(g, vis, u, ts))
  80.                 return false;
  81.         }
  82.     }
  83.     vis[v] = 2;
  84.     ts.push_back(v);
  85.     return true;
  86. }
  87.  
  88. vector<int> topsort(vector<vector<int>> &g) {
  89.     int n = (int)g.size();
  90.     vector<char> vis(n);
  91.     vector<int> ts;
  92.     for (int i = 0; i < n; ++i) {
  93.         if (!vis[i]) {
  94.             if (!ts_dfs(g, vis, i, ts)) {
  95.                 return {};
  96.             }
  97.         }
  98.     }
  99.     reverse(ts.begin(), ts.end());
  100.     return ts;
  101. }
  102.  
  103. vector<int> clear_edges(vector<int> &ts, vector<vector<int>> &g, vector<int> &tin, vector<int> &tout) {
  104.     int n = (int)g.size();
  105.     vector<vector<int>> ng(n);
  106.     vector<int> last(n, -1);
  107.     for (auto &v : ts) {
  108.         for (auto &u : g[v]) {
  109.             if (last[u] != -1) {
  110.                 if (!(tin[last[u]] < tin[v] && tout[last[u]] > tout[v])) {
  111.                     cout << "No\n";
  112.                     exit(0);
  113.                 }
  114.             }
  115.             last[u] = v;
  116.         }
  117.     }
  118.     for (int v = 0; v < n; ++v) {
  119.         if (last[v] == -1) continue;
  120.         ng[last[v]].push_back(v);
  121.     }
  122.     g = ng;
  123.     return last;
  124. }
  125.  
  126. void time_dfs(vector<vector<int>> &g, vector<char> &vis, int v, vector<int> &tin, vector<int> &tout, int &cur) {
  127.     vis[v] = 1;
  128.     tin[v] = cur++;
  129.  
  130.     for (auto &u : g[v]) {
  131.         if (!vis[u])
  132.             time_dfs(g, vis, u, tin, tout, cur);
  133.     }
  134.  
  135.     tout[v] = cur++;
  136. }
  137.  
  138. bool check_time(vector<vector<int>> &g, vector<char> &vis, int v, vector<int> &tin, vector<int> &tout) {
  139.     vis[v] = 1;
  140.     for (auto &u : g[v]) {
  141.         if (!(tin[v] < tin[u] && tout[v] > tout[u]))
  142.             return false;
  143.         if (!vis[u]) {
  144.             if (!check_time(g, vis, u, tin, tout))
  145.                 return false;
  146.         }
  147.     }
  148.     return true;
  149. }
  150.  
  151. void solve() {
  152.     int n, m;
  153.     cin >> n >> m;
  154.  
  155.     map<pii, char> used;
  156.  
  157.     vector<vector<int>> g(n);
  158.     for (int i = 0; i < m; ++i) {
  159.         int v, u;
  160.         cin >> v >> u, --v, --u;
  161.  
  162.         if (!used[{v, u}]) {
  163.             g[v].push_back(u);
  164.             used[{v, u}] = 1;
  165.         }
  166.     }
  167.  
  168.     if (!check_comp(g)) {
  169.         cout << "No\n";
  170.         return;
  171.     }
  172.  
  173.     vector<int> ts = topsort(g);
  174.  
  175.     if (ts.empty()) {
  176.         cout << "No\n";
  177.         return;
  178.     }
  179.  
  180.     vector<char> vis(n);
  181.     vector<int> tin(n), tout(n);
  182.     int cur = 0;
  183.     time_dfs(g, vis, ts[0], tin, tout, cur);
  184.  
  185.     vector<int> ans = clear_edges(ts, g, tin, tout);
  186.  
  187.     fill(vis.begin(), vis.end(), 0);
  188.     visit(g, vis, ts[0]);
  189.     if ((int)count(vis.begin(), vis.end(), 1) != n) {
  190.         cout << "No\n";
  191.         return;
  192.     }
  193.  
  194.     cout << "Yes\n";
  195.     for (auto &x : ans) {
  196.         if (x == -1)
  197.             cout << -1 << ' ';
  198.         else
  199.             cout << x + 1 << ' ';
  200.     }
  201.     cout << '\n';
  202. }
  203.  
  204. signed main() {
  205.     ios_base::sync_with_stdio(false);
  206.     cin.tie(nullptr);
  207.     cout << fixed << setprecision(9);
  208.     int t = 1;
  209.     //cin >> t;
  210.     while (t--) {
  211.         solve();
  212.     }
  213. }
  214.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement