Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int NMAX = 1e5 + 10;
- int n,m,was[NMAX];
- vector < int > v[NMAX];
- priority_queue < pair < int, int > > q;
- int main(){
- int i,j,x,y,node,grad;
- cin >> n >> m;
- for(i = 1 ; i <= m ; i++){
- cin >> x >> y;
- v[x].push_back(y);
- was[y]++;
- }
- ///in was[i] retirn cate muchii vin in nodul i
- ///nodurile in care vin 0 muchii pot fii oricat de la inceput, deci nu conteaza ordinea lor intre
- /// ele
- ///nodurile cu gradul intern 0 le afisez in ordine crescatoare
- ///acum se pune problema ce pozitii au nodurile ramase
- for(i = 1 ; i <= n ; i++)
- q.push(make_pair(-was[i], -i));
- while(!q.empty()){
- node = -q.top().second;
- grad = -q.top().first;
- q.pop();
- if(grad != was[node])
- continue;
- cout << node << " ";
- for(auto it: v[node]){
- was[it]--;///nu ne mai intereseaza cele deja afisate, deci e ca si cum nu ar fi existat
- q.push(make_pair(-was[it], -it));
- }
- }
- /// deoarece e graf aciclic, sigur vom avea la inceput noduri cu gradul intern 0
- /// si sigur dupa eliminarea lor raman alte noduri cu gradul intern 0
- /// de aici rezulta ca la momentul afisarii toate cele pe care le afisez au gradul intern 0
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement