Cod sursa(job #1781499)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 16 octombrie 2016 22:14:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

const int NMAX = 50050;
const int MMAX = 100010;

vector<int> G[NMAX];
int Q[NMAX], lenq = 0;
int N, M;
int grad[NMAX];

int main () {
    fin >> N >> M;
    int x, y;
    for (int i = 1; i <= M; i++) {
        fin >> x >> y;
        G[x].push_back(y);
        grad[y]++;
    }

    for (int i = 1; i <= N; i++) {
        if (grad[i] == 0) {
            Q[++lenq] = i;;
        }
    }
    for (int i = 1; i <= N; i++) {
        for (auto &it : G[Q[i]]) {
            grad[it]--;
            if (grad[it] == 0) {
                Q[++lenq] = it;
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        fout << Q[i] << " ";
    }
    fout << "\n";

    return 0;
}