abinash_hstu

Top Sort by DFS

Jan 16th, 2016
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.21 KB | None | 0 0
  1. //Abinash Ghosh(Om)
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cctype>
  5. #include <cmath>
  6. #include <cstring>
  7. #include <climits>
  8. #include <iostream>
  9. #include <iomanip>
  10. #include <vector>
  11. #include <list>
  12. #include <stack>
  13. #include <queue>
  14. #include <map>
  15. #include <set>
  16. #include <string>
  17. #include <utility>
  18. #include <sstream>
  19. #include <algorithm>
  20. #include <ctime>
  21. #include <cassert>
  22. using  namespace  std;
  23.  
  24. #define PI acos(-1.0)
  25. #define mem(a,b) memset(a,b,sizeof(a))
  26. #define gcd(a,b) __gcd(a,b)
  27. #define pb push_back
  28. #define mp make_pair
  29. #define x first
  30. #define y second
  31. #define Sort(x) sort(x.begin(),x.end())
  32. #define FOR(i, b, e) for(int i = b; i <= e; i++)
  33. #define FORR(i, b, e) for(int i = b; i >= e; i--)
  34. #define pr(x) cout<<x<<"\n"
  35. #define pr2(x,y) cout<<x<<" "<<y<<"\n"
  36. #define pr3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n";
  37. #define READ(f) freopen(f, "r", stdin)
  38. #define WRITE(f) freopen(f, "w", stdout)
  39.  
  40. typedef  long long ll;
  41. typedef  pair <int, int> pii;
  42. typedef  pair <double , double> pdd;
  43. typedef  pair <ll , ll > pll;
  44. typedef  vector <int> vi;
  45. typedef  vector <pii> vpii;
  46. typedef  vector <ll > vl;
  47. //ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  48. //ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  49.  
  50. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  51. //int dx[]={1,1,0,-1,-1,-1,0,1};
  52. //int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  53. //int dx[]={2,1,-1,-2,-2,-1,1,2};
  54. //int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  55.  
  56. #define MAX 100007
  57. #define EPS 1e-9
  58.  
  59.  
  60. bool vis[MAX];
  61. vi edge[MAX], topS;
  62. void dfs_visit(int u)
  63. {
  64.     vis[u]=1;
  65.     for(int i=0;i<(int)edge[u].size();i++){
  66.         int v=edge[u][i];
  67.         if(!vis[v])dfs_visit(v);
  68.     }
  69.     topS.pb(u);
  70. }
  71. void topsort(int node)
  72. {
  73.     mem(vis,0);
  74.     for(int i=0;i<node;i++)
  75.         if(!vis[i])dfs_visit(i);
  76.     reverse(topS.begin(),topS.end());
  77. }
  78. int main()
  79. {
  80.     int a,b,node,edges;
  81.     scanf("%d%d",&node,&edges);
  82.     for(int i=0; i<edges; i++)
  83.     {
  84.         scanf("%d %d",&a,&b);
  85.         edge[a].pb(b);
  86.     }
  87.     topsort(node);
  88.     return 0;
  89. }
  90. /*
  91. 9 9
  92. 0 1
  93. 1 2
  94. 0 3
  95. 5 6
  96. 5 7
  97. 6 7
  98. 8 7
  99. 6 3
  100. 3 2
  101.  
  102.  
  103. */
Advertisement
Add Comment
Please, Sign In to add comment