Advertisement
Guest User

Untitled

a guest
Apr 9th, 2020
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <string.h>
  5. #include <math.h>
  6. #include <map>
  7. #include <set>
  8. #include <vector>
  9.  
  10. #define MOD 998244353
  11. #define MAX_N 100005
  12. #define f first
  13. #define s second
  14.  
  15. using namespace std;
  16.  
  17. typedef pair<int, int> ii;
  18. typedef pair<ii, int> pii;
  19.  
  20. long long mod_pow(long long num, long long power)
  21. {
  22.     long long test;
  23.     for(test = 1; power; power >>= 1)
  24.     {
  25.         if (power & 1)
  26.             test = (test * num) % MOD;
  27.         num = (num * num) % MOD;
  28.     }
  29.  
  30.     return test;
  31. }
  32.  
  33. vector<int> con[MAX_N];
  34.  
  35. int vis[MAX_N], in[MAX_N];
  36. int N, M;
  37.  
  38. void solve() {
  39.     cin >> N >> M;
  40.  
  41.     int a, b;
  42.     for (int i = 0; i < M; i ++) {
  43.         cin >> a >> b;
  44.         con[b - 1].push_back(a - 1);
  45.     }
  46.  
  47.     for (int i = 0; i < N; i ++) {
  48.         for (int j = 0; j < con[i].size(); j ++) {
  49.             in[con[i][j]] ++;
  50.         }
  51.     }
  52.  
  53.     multiset<int> s;
  54.     for (int i = 0; i < N; i++)
  55.         if (in[i] == 0)
  56.             s.insert(-i);
  57.  
  58.     int cnt = 0;
  59.  
  60.     vector<int> top_order;
  61.  
  62.     while (!s.empty()) {
  63.         int u = -(*s.begin());
  64.         s.erase(s.begin());
  65.         top_order.push_back(u);
  66.  
  67.         // Iterate through all its neighbouring nodes
  68.         // of erased node u and decrease their in-degree
  69.         // by 1
  70.        
  71.         for (int i = 0; i < con[u].size(); i ++) {
  72.             in[con[u][i]] --;
  73.            
  74.             if (in[con[u][i]] == 0) {
  75.                 s.insert(-con[u][i]);
  76.             }
  77.         }
  78.        
  79.         cnt++;
  80.     }
  81.  
  82.     for (int i = top_order.size() - 1; i >= 0; i --)
  83.         cout << (top_order[i] + 1) << " ";
  84.    
  85.     cout << endl;
  86.     return;
  87. }
  88.  
  89. int main() {
  90.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  91.  
  92.     int T;
  93.     T = 1;
  94.    
  95.     for (int i = 0; i < T; i ++) {
  96.         solve();
  97.     }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement