Cod sursa(job #2406890)

Utilizator LucianTLucian Trepteanu LucianT Data 16 aprilie 2019 12:19:56
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int maxN=5e4+1;

int n,m;
vector<int> v[maxN];
int deg[maxN];

int main(){
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");

    f>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        f>>x>>y;
        v[x].push_back(y);
        deg[y]++;
    }

    queue<int> Que;
    for(int i=1;i<=n;i++){
        if(deg[i]==0){
            Que.push(i);
        }
    }

    while(!Que.empty()){
        int nod=Que.front();
        Que.pop();
        g<<nod<<" ";

        for(auto it:v[nod])
            if(deg[it]>0){
                deg[it]--;
                if(deg[it]==0){
                    Que.push(it);
                }
            }
    }

    return 0;
}