Advertisement
btdat2506

Untitled

Aug 23rd, 2020
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef int64_t ll;
  6. #define For(i, a, b) for(ll i = a; i <= b; i++)
  7.  
  8. bool valid = 1;
  9. ll n, m, visited[100010];
  10. vector <ll> edge[100010];
  11. stack <ll> tpsrt;
  12.  
  13. void dfs(ll u, ll color[])
  14. {
  15.     if (!valid) return;
  16.     color[u] = 1; //visited, but not done
  17.     for (ll v: edge[u])
  18.     if (color[v] == 0)
  19.         dfs(v, color);
  20.     else
  21.     if (color[v] == 1)
  22.         valid = 0;
  23.     color[u] = 2;
  24. }
  25.  
  26. bool isAcrylic()
  27. {
  28.     ll color[100010];
  29.     memset(color, 0, sizeof(color));
  30.     For(i, 1, n)
  31.     if (!color[i]) dfs(i, color);
  32.     return valid;
  33. }
  34.  
  35. void topo_sort(ll u)
  36. {
  37.     visited[u] = 1;
  38.     for(ll v: edge[u])
  39.     if (!visited[v])
  40.         topo_sort(v);
  41.     tpsrt.push(u);
  42. }
  43.  
  44. void process()
  45. {
  46.     if (isAcrylic())
  47.     {
  48.         For(i, 1, n)
  49.         if (!visited[i] && valid)
  50.             topo_sort(i);
  51.         while (!tpsrt.empty())
  52.         {
  53.             cout << tpsrt.top() << ' ';
  54.             tpsrt.pop();
  55.         }
  56.     }
  57.     else
  58.         cout << "IMPOSSIBLE" << "\n";
  59. }
  60.  
  61. void input()
  62. {
  63.     cin >> n >> m;
  64.     For(i, 1, m)
  65.     {
  66.         ll u, v;
  67.         cin >> u >> v;
  68.         edge[u].push_back(v);
  69.     }
  70. }
  71.  
  72. int main()
  73. {
  74.     /* freopen("test.in", "r", stdin);
  75.     freopen("test.ok", "w", stdout); */
  76.     input();
  77.     process();
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement