fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  9. #define int long long
  10. #define br << '\n'
  11. #define sp << ' '
  12.  
  13. vector<vector<int>> adj;
  14. vector<int> vis;
  15. stack<int> stk;
  16.  
  17. bool dfs(int n)
  18. {
  19.     vis[n] = 1;
  20.  
  21.     for (auto v : adj[n])
  22.     {
  23.         if (vis[v] == 0)
  24.         {
  25.             if (dfs(v))
  26.                 return true;
  27.         }
  28.         else if (vis[v] == 1)
  29.         {
  30.             return true;
  31.         }
  32.     }
  33.  
  34.     stk.push(n);
  35.     vis[n] = 2;
  36.     return false;
  37. }
  38.  
  39. void solve()
  40. {
  41.     int n, e;
  42.     while (cin >> n >> e && (n != 0 || e != 0))
  43.     {
  44.         adj.assign(n + 1, {});
  45.         vis.assign(n + 1, 0);
  46.         while (stk.size())
  47.         {
  48.             stk.pop();
  49.         }
  50.  
  51.         for (int i = 0, f, t; i < e; i++)
  52.         {
  53.             cin >> f >> t;
  54.             adj[f].emplace_back(t);
  55.         }
  56.  
  57.         bool flag = false;
  58.         for (int i = 1; i <= n; i++)
  59.         {
  60.             if (!vis[i])
  61.             {
  62.                 if (dfs(i))
  63.                 {
  64.                     flag = true;
  65.                     cout << "IMPOSSIBLE" << '\n';
  66.                     break;
  67.                 }
  68.             }
  69.         }
  70.  
  71.         while (stk.size() and !flag)
  72.         {
  73.             cout << stk.top() << '\n';
  74.             stk.pop();
  75.         }
  76.     }
  77. }
  78.  
  79. int32_t main()
  80. {
  81.     ios_base::sync_with_stdio(false);
  82.     cin.tie(nullptr);
  83.     cout.tie(nullptr);
  84.  
  85.     // freopen("in.txt", "rt", stdin);
  86.     // freopen("out.txt", "wt", stdout);
  87.  
  88.     int t = 1;
  89.     // cin >> t;
  90.     while (t--)
  91.     {
  92.         solve();
  93.     }
  94.     return 0;
  95. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
1 0
stdout
copy 
1
https://ideone.com/aBXlYn
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!