Cod sursa(job #2413369)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 23 aprilie 2019 12:44:11
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
#define NMAX 50001
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector <int> G[NMAX];
int N, M;
int x, y;
int gradi[NMAX];
queue <int> Que;
vector <int> sol;

int main() {
    f >> N >> M;
    for (int i = 0; i < M; ++i) {
        f >> x >> y;
        gradi[y]++;
        G[x].push_back(y);
    }
    for (int i = 1; i <= N; ++i) {
        if (gradi[i] == 0)
            Que.push(i);
    }
    while (!Que.empty()) {
        x = Que.front();
        Que.pop();
        g << x << ' ';
        for (auto y : G[x]) {
            gradi[y]--;
            if (gradi[y] == 0) Que.push(y);
        }
    }
    return 0;
}