Cod sursa(job #2156586)

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

list<int> adjList[NMAX];
bitset<NMAX> vis;

int Stack[NMAX];
int nodesCnt, edgesCnt, StackLen;

inline void readData(){

    fin >> nodesCnt >> edgesCnt;

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

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

void topoSort(int node){

    vis[node] = true;
    for(const auto &nextNode : adjList[node])
        topoSort(nextNode);
    Stack[++StackLen] = node;
}

inline void getOrder(){

    int node;
    for(node = 1; node <= nodesCnt; ++node)
        if(!vis[node])
            topoSort(node);
}

inline void print(){

    while(StackLen){

        fout << Stack[StackLen] << ' ';
        --StackLen;
    }
}

int main(){

    readData();
    getOrder();
    print();
}