Cod sursa(job #2574808)

Utilizator CristiVintilacristian vintila CristiVintila Data 6 martie 2020 10:05:04
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 50005
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n, m, nex[NMAX], q[NMAX], k;
vector<int> gr[NMAX];

void citire() {
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        fin >> x >> y;
        gr[x].push_back(y);
        nex[y]++;
    }
}

void rezolvare() {
    for (int i = 1; i <= n; ++i)
        if (nex[i] == 0)
            q[++k] = i;

    for (int i = 1; i <= n; ++i) {
        int x = q[i];
        for (int j = 0; j < gr[x].size(); j++) {
            nex[gr[x][j]]--;
            if (nex[gr[x][j]] == 0)
                q[++k] = gr[x][j];
        }
    }
}

int main(int argc, const char * argv[]) {
    citire();
    rezolvare();
    for (int i = 1; i <= n; ++i)
        fout << q[i] << " ";
}