TrickmanOff

Untitled

Oct 25th, 2020
836
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //#pragma optimization_level 3
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  3. //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <fstream>
  7. #include <vector>
  8. #include <queue>
  9. #include <functional>
  10. #include <set>
  11. #include <map>
  12. #include <math.h>
  13. #include <cmath>
  14. #include <string>
  15. //#include <random>
  16. //#include <unordered_set>
  17. //#include <unordered_map>
  18. #include <bitset>
  19. #include <string.h>
  20. #include <stack>
  21. #include <assert.h>
  22. #include <list>
  23. #include <time.h>
  24. //#include <tuple>
  25. #include <memory>
  26. //#include <chrono>
  27. using namespace std;
  28. //
  29. #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
  30. //#define cin in
  31. //#define cout out
  32. #define ll long long
  33. #define db double
  34. #define ld long double
  35. #define uset unordered_set
  36. #define umap unordered_map
  37. #define ms multiset
  38. #define pb push_back
  39. //#define pq priority_queue
  40. #define umap unordered_map
  41. #define uset unordered_set
  42. #define ull unsigned long long
  43. #define pii pair<int, int>
  44. #define pll pair<ll, ll>
  45. #define pdd pair<ld, ld>
  46. #define pnn pair<Node*, Node*>
  47. #define uid uniform_int_distribution
  48. #define PI acos(-1.0)
  49. //#define sort(a, b) sort(a.begin(), a.end(), b())
  50. //mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  51. ifstream in("input.txt");
  52. ofstream out("output.txt");
  53.  
  54. const int MAX_N = 2e5;
  55.  
  56. vector<int> pr[MAX_N];
  57.  
  58. int n, m;
  59.  
  60. int out_degr[MAX_N];
  61. bool used[MAX_N];  // is already in ans
  62.  
  63. void input() {
  64.     cin >> n >> m;
  65.     vector<pii> edges(m);
  66.  
  67.     for (int i = 0; i < m; ++i) {
  68.         int a, b;
  69.         cin >> a >> b;
  70.         edges[i] = make_pair(a-1, b-1);
  71.     }
  72.     sort(edges.begin(), edges.end());
  73.     edges.resize(unique(edges.begin(), edges.end()) - edges.begin());
  74.     m = edges.size();
  75.  
  76.     for (int i = 0; i < m; ++i) {
  77.         int a = edges[i].first, b = edges[i].second;
  78.         pr[b].push_back(a);
  79.     }
  80. }
  81.  
  82. // проход по предкам
  83. void dfs(int v, int& cnt) {
  84.     for (int _ = 0; _ < pr[v].size(); ++_) {
  85.         int p = pr[v][_];
  86.  
  87.         if (!used[p]) {
  88.             cnt += (out_degr[p] == 0);  // первый раз пришли в вершину
  89.             ++out_degr[p];
  90.             dfs(p, cnt);
  91.         }
  92.     }
  93. }
  94.  
  95. vector<int> ans;
  96.  
  97. // в каждой компоненте макс. вершина с исх. степенью 0
  98. void solve(int v0, int& ins_pos) {
  99.     int pos = ins_pos;
  100.     dfs(v0, pos);
  101.     ins_pos = pos + 1;
  102.     // pos - начиная с какого ставим
  103.     // ins_pos - первый свободный в ans
  104.  
  105.     priority_queue<int> pq;
  106.     pq.push(v0);
  107.  
  108.     while (!pq.empty()) {
  109.         int v = pq.top();
  110.         pq.pop();
  111.  
  112.         for (int _ = 0; _ < pr[v].size(); ++_) {
  113.             int p = pr[v][_];
  114.             if (!used[p] && --out_degr[p] == 0)
  115.                 pq.push(p);
  116.         }
  117.  
  118.         ans[pos--] = v;
  119.         used[v] = 1;
  120.     }
  121. }
  122.  
  123. int main() {
  124.     input();
  125.     ans.resize(n);
  126.     int pos = 0;
  127.  
  128.     memset(out_degr, 0, sizeof(out_degr));
  129.     memset(used, 0, sizeof(used));
  130.  
  131.     for (int v = 0; v < n; ++v) {
  132.         if (!used[v])
  133.             solve(v, pos);
  134.     }
  135.  
  136.     for (int _ = 0; _ < n; ++_)
  137.         cout << ans[_] + 1 << ' ';
  138. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×