Saleh127

UVA 11686

Jul 6th, 2021 (edited)
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.69 KB | None | 0 0
  1. /*
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define endl "\n"
  6. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  7. vector<ll>ans;
  8. vector<ll>g[200000];
  9. ll v[200000];
  10. ll cycle=0;
  11. void dfs(ll c)
  12. {
  13. v[c]=2;
  14. for(auto dd:g[c])
  15. {
  16. if(v[dd]==2)
  17. {
  18. cycle=1;
  19. }
  20. if(v[dd]==0)
  21. {
  22. dfs(dd);
  23. }
  24. }
  25.  
  26. v[c]=1;
  27. ans.push_back(c);
  28. }
  29.  
  30. int main()
  31. {
  32. ios_base::sync_with_stdio(0);
  33. cin.tie(0);
  34. cout.tie(0);
  35.  
  36. ll n,m,i,j,k,l;
  37.  
  38. while(cin>>n>>m)
  39. {
  40. if(n==0 && m==0) break;
  41.  
  42. for(i=0; i<m; i++)
  43. {
  44. cin>>j>>k;
  45. g[j].push_back(k);
  46. }
  47.  
  48. for(i=1; i<=n; i++)
  49. {
  50. if(v[i]==0)
  51. {
  52. dfs(i);
  53. }
  54. }
  55.  
  56. if(cycle)
  57. {
  58. cout<<"IMPOSSIBLE"<<endl;
  59. }
  60.  
  61. else
  62. {
  63. reverse(ans.begin(),ans.end());
  64.  
  65. for(auto dd:ans)
  66. {
  67. cout<<dd<<endl;
  68. }
  69. }
  70.  
  71.  
  72. cycle=0;
  73. for(i=0;i<200000;i++)
  74. {
  75. g[i].clear();
  76. }
  77. ans.clear();
  78. memset(v,0,sizeof v);
  79. }
  80.  
  81. return 0;
  82. }
  83.  
  84. */
  85.  
  86.  
  87. #include <bits/stdc++.h>
  88. using namespace std;
  89. #define ll long long
  90. #define endl "\n"
  91. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  92. vector<ll>ans;
  93. vector<ll>g[200000];
  94. ///bool v[200000];
  95. map<ll,ll>x;
  96. ll n,m;
  97. void bfs()
  98. {
  99. queue<ll>q;
  100.  
  101. for(ll i=1;i<=n;i++)
  102. {
  103. if(x[i]==0)
  104. {
  105. q.push(i);
  106. }
  107. }
  108.  
  109. while(q.empty()==false)
  110. {
  111. ll u=q.front();
  112. q.pop();
  113.  
  114. ans.push_back(u);
  115.  
  116. for(auto v:g[u])
  117. {
  118. x[v]--;
  119. if(x[v]==0)
  120. {
  121. q.push(v);
  122. }
  123. }
  124. }
  125. }
  126.  
  127. int main()
  128. {
  129. ios_base::sync_with_stdio(0);
  130. cin.tie(0);
  131. cout.tie(0);
  132.  
  133. ll i,j,k,l;
  134.  
  135. while(cin>>n>>m)
  136. {
  137. if(n==0 && m==0) break;
  138.  
  139. for(i=0; i<m; i++)
  140. {
  141. cin>>j>>k;
  142. g[j].push_back(k);
  143. x[k]++;
  144. }
  145.  
  146. bfs();
  147.  
  148. if(ans.size()!=n)
  149. {
  150. cout<<"IMPOSSIBLE"<<endl;
  151. }
  152.  
  153. else
  154. {
  155. for(i=0;i<ans.size();i++)
  156. {
  157. cout<<ans[i]<<endl;
  158. }
  159. }
  160.  
  161. x.clear();
  162. ans.clear();
  163.  
  164. for(i=0;i<n+100;i++)
  165. {
  166. g[i].clear();
  167. }
  168. }
  169.  
  170.  
  171. return 0;
  172. }
  173.  
  174.  
Add Comment
Please, Sign In to add comment