Guest User

Sorry for some extra-code :(

a guest
Oct 19th, 2015
260
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 KB | None | 0 0
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #define _USE_MATH_DEFINES
  3.  
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <vector>
  10. #include <string>
  11. #include <cstring>
  12. #include <sstream>
  13. #include <set>
  14. #include <map>
  15. #include <queue>
  16. #include <memory.h>
  17. #include <ctime>
  18.  
  19. using namespace std;
  20.  
  21. #pragma comment(linker, "/STACK:128000000")
  22.  
  23. typedef pair<int, int> pii;
  24. typedef long long int64;
  25. typedef pair<int64, int64> pii64;
  26. typedef vector<int> vi;
  27. typedef vector<vi> vvi;
  28. typedef vector<pii> vpii;
  29. typedef vector<vpii> vvpii;
  30. typedef pair<int,pii> piii;
  31. typedef pair<int64,pii> piii64;
  32. typedef pair<pii,pii> piiii;
  33.  
  34. #define y1 dsjfksdj_fks
  35. #define y2 alksaad_sa
  36. #define y0 _sdkfsjfs__
  37.  
  38. #define tm _dskfjskdfjksdf
  39.  
  40. int n, m;
  41. vvi g;
  42. vector <int> e;
  43. vector <int> was;
  44. vector <int> used;
  45. vector <int> cur;
  46. vector <int> res;
  47. priority_queue <int> q;
  48.  
  49. inline void init()
  50. {
  51.     scanf("%d%d", &n, &m);
  52.     g.resize(n);
  53.     was.assign(n, 0);
  54.     e.assign(n, 0);
  55.     used.assign(n, 0);
  56.     int x, y;
  57.     for (int i = 0; i < m; ++i)
  58.     {
  59.         scanf("%d%d", &x, &y);
  60.         --x, --y;
  61.         g[y].push_back(x);
  62.     }
  63.     for (int i = 0; i < n; ++i)
  64.         if (g[i].size())
  65.             sort(g[i].begin(), g[i].end());
  66. }
  67.  
  68. void dfs(int x)
  69. {
  70.     used[x] = 1;
  71.     int k = (int)g[x].size();
  72.     for (int i = 0; i < k; ++i)
  73.     {
  74.         int y = g[x][i];
  75.         if (was[y]) continue;
  76.         ++e[y];
  77.         if (used[y]) continue;
  78.         dfs(y);
  79.     }
  80. }
  81.  
  82. inline void qadd(int x)
  83. {
  84.     q.push(x);
  85. }
  86.  
  87. int main()
  88. {
  89.     //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  90.  
  91.     init();
  92.  
  93.     for (int i = 0; i < n; ++i)
  94.     {
  95.         if (was[i]) continue;
  96.         dfs(i);
  97.         qadd(i);
  98.         while (!q.empty())
  99.         {
  100.             int x = q.top();
  101.             was[x] = 1;
  102.             q.pop();           
  103.             cur.push_back(x);
  104.             int k = (int)g[x].size();
  105.             for (int j = 0; j < k; ++j)
  106.             {
  107.                 int y = g[x][j];
  108.                 --e[y];
  109.                 if (e[y]) continue;
  110.                 qadd(y);
  111.             }
  112.         }
  113.         while (cur.size())
  114.         {
  115.             res.push_back(cur.back());
  116.             cur.pop_back();
  117.         }
  118.     }
  119.  
  120.     for (int i = 0; i < n; ++i)
  121.         printf("%d ", res[i] + 1);
  122.    
  123.     return 0;
  124. }
Advertisement
Add Comment
Please, Sign In to add comment