Advertisement
Guest User

Untitled

a guest
Jan 27th, 2020
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int NMAX = 1e5 + 10;
  6. int n,m,was[NMAX];
  7. vector < int > v[NMAX];
  8. priority_queue < pair < int, int > > q;
  9.  
  10. int main(){
  11. int i,j,x,y,node,grad;
  12. cin >> n >> m;
  13. for(i = 1 ; i <= m ; i++){
  14. cin >> x >> y;
  15. v[x].push_back(y);
  16. was[y]++;
  17. }
  18. ///in was[i] retirn cate muchii vin in nodul i
  19.  
  20. ///nodurile in care vin 0 muchii pot fii oricat de la inceput, deci nu conteaza ordinea lor intre
  21. /// ele
  22.  
  23. ///nodurile cu gradul intern 0 le afisez in ordine crescatoare
  24.  
  25. ///acum se pune problema ce pozitii au nodurile ramase
  26. for(i = 1 ; i <= n ; i++)
  27. q.push(make_pair(-was[i], -i));
  28.  
  29. while(!q.empty()){
  30. node = -q.top().second;
  31. grad = -q.top().first;
  32. q.pop();
  33.  
  34. if(grad != was[node])
  35. continue;
  36.  
  37. cout << node << " ";
  38.  
  39. for(auto it: v[node]){
  40. was[it]--;///nu ne mai intereseaza cele deja afisate, deci e ca si cum nu ar fi existat
  41. q.push(make_pair(-was[it], -it));
  42. }
  43.  
  44. }
  45.  
  46. /// deoarece e graf aciclic, sigur vom avea la inceput noduri cu gradul intern 0
  47. /// si sigur dupa eliminarea lor raman alte noduri cu gradul intern 0
  48.  
  49. /// de aici rezulta ca la momentul afisarii toate cele pe care le afisez au gradul intern 0
  50.  
  51. return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement