Cod sursa(job #2479882)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 24 octombrie 2019 17:17:45
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int NMAX=1e5+4;

int n,m,dg[NMAX];
vector <int> g[NMAX],lvl[NMAX];

int main(){
    int x,y,node;
    fin>>n>>m;
    for(int i=0;i<m;++i){
        fin>>x>>y;
        g[x].push_back(y);
        ++dg[y];
    }
    for(int i=1;i<=n;++i)
        if(!dg[i]){
            lvl[1].push_back(i);
        }
    for(int i=1;i<=n && lvl[i].size();++i){
        for(auto node:lvl[i]){
            dg[node]=-1;
            for(auto it:g[node]){
                --dg[it];
                if(!dg[it]){
                    lvl[i+1].push_back(it);
                }
            }
        }
    }
    for(int i=1;i<=n && lvl[i].size();++i){
        for(auto it:lvl[i]){
            fout<<it<<' ';
        }
    }
    return 0;
}