Cod sursa(job #2446690)

Utilizator AndreiJJIordan Andrei AndreiJJ Data 10 august 2019 14:16:15
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector <int> L[50005];
priority_queue<int> q;
int d[50005];

int n, m;

void Read ()
{
    fin >> n >> m;
    int i, j;
    while (m--)
    {
        fin >> i >> j;
        L[i].push_back(j);
        d[j]++;
    }
}

void SortTop()
{
    int i, k;
    for (i = 1; i <= n; i++)
        if (d[i] == 0)
            q.push(-i);
    while (!q.empty())
    {
        k = -q.top();
        q.pop();
        fout << k << " ";
        for (auto j : L[k])
        {
            d[j]--;
            if (d[j] == 0) q.push(-j);
        }
    }

}


int main()
{
    Read();
    SortTop();
    return 0;
}