Cod sursa(job #2156577)

Utilizator DawlauAndrei Blahovici Dawlau Data 8 martie 2018 20:24:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream>
#include<list>
#include<deque>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int NMAX = 5e4 + 5;

list<int> adjList[NMAX];
deque<int> Queue;

int inDegree[NMAX];
int nodesCnt, edgesCnt;

inline void readData(){

    fin >> nodesCnt >> edgesCnt;

    int from, to;
    while(edgesCnt--){

        fin >> from >> to;
        adjList[from].push_back(to);
        ++inDegree[to];
    }
}

inline void topoSort(){

    int node;
    for(node = 1; node <= nodesCnt; ++node)
        if(inDegree[node] == 0)
            Queue.push_back(node);

    while(!Queue.empty()){

        node = Queue.front();
        Queue.pop_front();
        fout << node << ' ';

        for(const auto &nextNode : adjList[node]){

            --inDegree[nextNode];
            if(inDegree[nextNode] == 0)
                Queue.push_back(nextNode);
        }
    }
}

int main(){

    readData();
    topoSort();
}