Advertisement
Ginger_samurai

topSort

Jul 14th, 2020
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. #include<vector>
  2. #include <string>
  3. #include<algorithm>
  4. #include <iostream>
  5. #include <queue>
  6. #include<set>
  7. #include<stack>
  8. #include<cmath>
  9. #include<math.h>
  10. #include<map>
  11. #include<unordered_map>
  12. #include<unordered_map>
  13. using namespace std;
  14. typedef long long ll;
  15. typedef pair<long long, long long> pll;
  16. #define mp make_pair
  17. #define fi(b, c) for(auto i = b; i <= c; i++)
  18. #define fj(b, c) for(auto j = b; j <= c; j++)
  19. #define fk(b, c) for(auto k = b; k <= c; k++)
  20. #define fq(b, c) for(auto q = b; q <= c; q++)
  21. #define fw(b, c) for(auto w = b; w <= c; w++)
  22. #define fim(b, c) for(auto i = b; i >= c; i--)
  23. #define fjm(b, c) for(auto j = b; j >= c; j--)
  24. #define fkm(b, c) for(auto k = b; k >= c; k--)
  25. #define all(a) a.begin(), a.end()
  26. #define rall(a) a.rbegin(), a.rend()
  27. #define sz(a) (ll)(a.size())
  28. #define fs first
  29. #define sd second
  30. #define endl "\n"
  31. #define cin(a) for(ll o = 0; o<a.size(); o++) cin>>a[o];
  32. #define cout(a) for(ll o = 0; o<a.size(); o++) cout<<a[o]<<" ";
  33. const ll inf = 1e9 + 123, llinf = 1e18 + 123;
  34. void xru(){
  35.  setlocale(LC_ALL, "rus");
  36.  /*freopen(".in", "r", stdin);
  37.  freopen(".out", "w", stdout);*/
  38.  ios_base::sync_with_stdio(false);
  39.  cin.tie(NULL);
  40.  cout.tie(NULL);
  41. }
  42. void run(){
  43.     cout<<endl;
  44.     system("pause");
  45. }
  46.  
  47. void dfs(ll x, vector< vector<ll> >& g, vector< bool >& used, vector< ll >& ans){
  48.     used[x] = true;
  49.     for (ll v: g[x]) {
  50.         if(!used[v]){
  51.             dfs(v, g, used, ans);
  52.         }
  53.     }
  54.     ans.push_back(x);
  55. }
  56.  
  57. void topsort(vector< vector<ll> >& g, vector< bool >& used, vector< ll >& ans){
  58.     fi(0, sz(g)-1){
  59.         if(!used[i]){
  60.             dfs(i, g, used, ans);
  61.         }
  62.     }
  63.     reverse(all(ans));
  64. }
  65.  
  66. int main() {
  67.     ll n, m;
  68.     cin >> n >> m;
  69.     vector< vector<ll> > g(n);
  70.     vector< bool > used(n, false);
  71.     vector< ll > ans;
  72.     fi (0, m-1) {
  73.         ll x, y;
  74.         cin >> x >> y;
  75.         x--, y--;
  76.         g[x].push_back(y);
  77.     }
  78.     topsort(g, used, ans);
  79.     cout (ans);
  80.     run();
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement