Cod sursa(job #2209707)

Utilizator axelteoTeodor Dutu axelteo Data 4 iunie 2018 13:38:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>

using namespace std;

#define NMAX 50001

queue<int> q;
int numNodes, numEdges, inDegree[NMAX];
vector<list<int>> adjList(NMAX);

ifstream fIn("sortaret.in");
ofstream fOut("sortaret.out");

int main(void) {
    int x, y, currNode;
    fIn >> numNodes >> numEdges;

    for(register int i = 0; i < numEdges; ++i) {
        fIn >> x >> y;
        adjList[x].push_back(y);
        ++inDegree[y];
    }

    for(int i = 1; i <= numNodes; ++i) {
        if (!inDegree[i]) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        currNode = q.front();
        q.pop();

        fOut << currNode << ' ';

        for_each(adjList[currNode].begin(), adjList[currNode].end(), [](int node) {
            if (!--inDegree[node]) {
                q.push(node);
            }
        });
    }
    fOut << '\n';

    fIn.close();
    fOut.close();
    return 0;
}