Advertisement
istinishat

topological_sort

Jun 3rd, 2016
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <queue>
  5. #include <vector>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. #define si(a) scanf("%d",&a)
  11. #define f first
  12. #define s second
  13. #define mp(a,b) make_pair(a,b)
  14. #define MAX 1005
  15.  
  16. int vis[MAX];
  17. vector<int> graph[MAX];
  18. vector<int> sorted_ara;
  19.  
  20. void go(int now)
  21. {
  22.     if(vis[now])
  23.         return ;
  24.     vis[now]=1;
  25.     for(int i=0;i<graph[now].size();i++)
  26.         go(graph[now][i]);
  27.     sorted_ara.push_back(now);
  28. }
  29.  
  30. int main()
  31. {
  32.     //freopen("input","r",stdin);
  33.     int n,m,i;
  34.     si(n);si(m);
  35.     for(i=0;i<m;i++){
  36.         int u,v;
  37.         si(u);si(v);
  38.         u--;v--;
  39.         graph[u].push_back(v);
  40.     }
  41.     for(i=0;i<n;i++)
  42.         go(i);
  43.     reverse(sorted_ara.begin(),sorted_ara.end());
  44.     for(i=0;i<n;i++)
  45.         cout<<sorted_ara[i]+1<<" ";
  46.     cout<<endl;
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement