TrickmanOff

Untitled

Oct 25th, 2020
743
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