Cod sursa(job #2241404)

Utilizator Raoul_16Raoul Bocancea Raoul_16 Data 15 septembrie 2018 18:59:57
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
const std :: string programName = "sortaret";
std :: ifstream f(programName + ".in");
std :: ofstream g(programName + ".out");
const int NMAX = 5E4;
int N, M, grade[NMAX + 5], queue[NMAX + 5];
std :: vector <int> Graph[NMAX + 5];
void read(void);
void write(void);
void topoSort(void);
int main(void) {
    read();
    topoSort();
    write();
    return 0x0;
}
void read(void) {
    f >> N >> M;
    while (M--) {
        int x, y;
        f >> x >> y;
        Graph[x].push_back(y);
        grade[y]++;
    }
}
void write(void) {
    for (int i = 1; i <= N; i++)
        g << queue[i] << ' ';
}
void topoSort(void) {
    int k(1);
    for (; k <= N; k++)
        if(!grade[k])
            queue[++queue[0]] = k;
    for (int i = 1; i <= N; i++) {
        k = queue[i];
        for (std :: vector <int> :: iterator it = Graph[k].begin(); it != Graph[k].end(); ++it) {
            grade[*it]--;
            if (!grade[*it])
                queue[++queue[0]] = *it;
        }
    }
}