Cod sursa(job #2529490)

Utilizator cip_ionescuCiprian Ionescu cip_ionescu Data 23 ianuarie 2020 16:23:51
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define MAX_N 50000

using std::cin;
using std::cout;

std::vector<int> g[1 + MAX_N];
int p[1 + MAX_N];

int main(int argc, char const *argv[])
{
    std::ifstream fin("sortaret.in");
    std::ofstream fout("sortaret.out");

    int n, m, x, y;

    fin >> n >> m;
    for (int i = 1 ; i <= m ; i++) {
        fin >> x >> y;
        g[x].push_back(y);
        p[y]++;
    }

    std::queue<int> q;
    for (int i = 1 ; i <= n ; i++)
        if (p[i] == 0) q.push(i);
    
    while (!q.empty()) {
        fout << q.front() << ' ';
        for (const auto &it : g[q.front()]) {
            p[it]--;
            if (!p[it]) q.push(it);
        }
        q.pop();
    }
    return 0;
}