Cod sursa(job #1533576)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 22 noiembrie 2015 18:43:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

int main()
{
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int n,m;
    fin>>n>>m;

    vector<vector<int>> Adj(n+1);
    vector<int> ingr(n+1,0);

    for(int i=0;i<m;++i){
        int x,y; fin>>x>>y;
        Adj[x].push_back(y);
        ++ingr[y];
    }

    stack<int> nullgr;
    for(int i=1;i<=n;++i)
        if(ingr[i]==0) nullgr.push(i);

    while(!nullgr.empty()){
        int v = nullgr.top();
        nullgr.pop();
        fout<<v<<' ';

        for(auto it=Adj[v].begin(); it!=Adj[v].end(); ++it)
            if(--ingr[*it] == 0)
                nullgr.push(*it);
    }

    fout<<'\n';
}