Cod sursa(job #2667755)

Utilizator CharmichlesAndrei Brihac Charmichles Data 3 noiembrie 2020 20:00:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 50001;

vector<int> adj[NMAX];
int grad_int[NMAX], q[NMAX], qsize;

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        grad_int[y]++;
    }
    fin.close();

    for (int i = 1; i <= n; i++) {
        if (grad_int[i] == 0) {
            q[++qsize] = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int nod : adj[q[i]]) {
            grad_int[nod]--;
            if (grad_int[nod] == 0) {
                q[++qsize] = nod;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        fout << q[i] << ' ';
    }
    fout << '\n';
    fout.close();
    return 0;
}