fork download
copy 
  1. /* THOU SHALL BE REWARDED DESERVINGLY */
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define int long long
  5. #define f first;
  6. #define s second
  7. #define mp make_pair
  8. #define pb push_back
  9.  
  10. #define print(x) cout<<x<<"\n"
  11. #define debug(x) cout<<#x<<" "<<x<<"\n"
  12. #define yes cout<<"YES\n"
  13. #define no  cout<<"NO\n"
  14. #define nl  cout<<"\n";
  15. #define uniq(v) (v).erase(unique(all(v)),(v).end())
  16. #define sum(a) (accumulate ((a).begin(), (a).end(), 0ll))
  17. #define minv(a)	(*min_element((a).begin(), (a).end()))
  18. #define maxv(a)	(*max_element((a).begin(), (a).end()))
  19. #define mina(a,n) (*min_element(a, a+n))
  20. #define maxa(a,n) (*max_element(a, a+n))
  21. #define mni(a) (min_element((a).begin(), (a).end())-(a).begin())
  22. #define mxi(a) (max_element((a).begin(), (a).end())-(a).begin())
  23. #define lb(a, x) (lower_bound((a).begin(), (a).end(), (x))-(a).begin())
  24. #define ub(a, x) (upper_bound((a).begin(), (a).end(), (x))-(a).begin())
  25. #define all(x) (x).begin(), (x).end()
  26. #define rep(i,a,n) for(int i=a; i<n; i++)
  27. #define per(i,a,n) for(int i=n-1; i>= a; i--)
  28. #define repv(itr, v) for(auto itr=v.begin(); itr!=v.end(); itr++)
  29. #define fnd(v, x) find(v.begin(), v.end(), x)!=v.end()
  30. #define printv(v) for(auto e : v) cout<<e<<" "
  31. #define pushv(v, n) rep(i,0,n) cin>>v[i]
  32. #define bsearch(v, x) binary_search(v.begin(), v.end(), x)
  33. #define uniq(v)	(v).erase(unique(all(v)),(v).end())
  34. #define sz(x) ((int)(x).size())
  35. #define eps 1e-9
  36.  
  37.  
  38. typedef vector<int> vi;
  39. typedef map<int, int> mi;
  40.  
  41.  
  42. const int mod = 1e9+7;
  43. const int inf = (int)1e9;
  44. const int INF=(int) 1e18;
  45. const int N = 3e5 + 5;
  46.  
  47. vector< vector<int> >tr;
  48. int indeg[200200];
  49. int vis[200200];
  50. int stak[200020];
  51. double ways[200200];
  52.  
  53. bool dfs(int node)
  54. {
  55. 	vis[node]=1;
  56. 	stak[node]=1;
  57.  
  58. 	for(auto child : tr[node])
  59. 	{
  60. 		if(!vis[child])
  61. 		{
  62. 			 vis[child]=1;
  63. 			   if(dfs(child)) return 1;
  64. 		}
  65. 		if(stak[child]) return 1;
  66.  
  67. 	}
  68.  
  69. 	//vis[node]=0;
  70. 	stak[node]=0;
  71.  
  72. 	return 0;
  73. }
  74.  
  75.  
  76.  
  77. bool iscycle(int node)
  78. {
  79. 	return dfs(node);
  80. }
  81.  
  82.  
  83.  
  84.  
  85. int32_t main()
  86. {
  87. 	cin.sync_with_stdio(false);
  88. 	cin.tie(0); cout.tie(0);
  89.  
  90.  
  91.     int tt = 1;   //cin>>tt;
  92.  
  93.     while(tt--)
  94.     {
  95. 		int n,m,r,u,v; cin>>n>>m;
  96.         //vi a(n); pushv(a, n);
  97.  
  98.         tr.resize(n+1);
  99.  
  100.         rep(i,0,m)
  101.         {
  102.         	cin>>u>>v;
  103.         	tr[u].pb(v);
  104.         	//tr[v].pb(u);
  105.         	indeg[v]++;
  106.         	//outdeg[u]++;
  107.  
  108.         }
  109.  
  110.         //ways[r]=1;
  111.  
  112.         bool bb=0;
  113.  
  114.  
  115.         queue <int> q;
  116.  
  117.         vector<int> init;
  118.  
  119.         rep(i,1,n+1)
  120.         {
  121.         	if(indeg[i]==0) { q.push(i); init.pb( i);}
  122.         }
  123.  
  124.          rep(i,0,sz(init)) if(iscycle(init[i]))
  125.         {
  126.         	print("IMPOSSIBLE"); return 0;
  127.         }
  128.  
  129.         vector<int>ans;
  130.  
  131.         while(!q.empty())
  132.         {
  133.         	int curr=q.front();
  134.         	q.pop();
  135.         	ans.pb(curr);
  136.  
  137.         	for( auto child : tr[curr])
  138.         	{
  139.         		indeg[child]--;
  140.         		//ways[child]= ways[curr]*1.0/outdeg[curr];
  141.  
  142.         		if(indeg[child]==0)
  143.         		 q.push(child);
  144.         	}
  145.  
  146.  
  147.         }
  148.  
  149.         if(sz(ans)!=n)
  150.         {
  151.         	print("IMPOSSIBLE"); return 0;
  152.         }
  153.  
  154.         for(auto x : ans) cout<<x<<" ";
  155.  
  156.  
  157.     }
  158.     return 0;
  159. }
Success #stdin #stdout 0.01s 5700KB
comments (?)
stdin
copy 
10 20
8 5
2 3
10 1
9 1
6 3
3 1
6 5
8 1
2 5
7 2
7 1
7 8
4 2
10 5
9 2
3 5
6 8
1 5
10 8
7 10
stdout
copy 
4 6 7 9 10 2 8 3 1 5
https://ideone.com/GR0Lgs
language:
C++14 (clang 8.0)
created:
1 year 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!