Cod sursa(job #2415231)

Utilizator raduandreicaRadu Andreica raduandreica Data 25 aprilie 2019 17:18:05
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

unsigned int N , M , deg[50010];

int main()
{
    fin >> N >> M;
    vector <vector <int>> G(50010);
    queue<int> a;

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

    for(int i=1 ; i<=N ; i++)
        if(deg[i] == 0)
            a.push(i);

    while(!a.empty())
    {
        int aux;
        fout << a.front() << " ";
        aux=a.front();
        a.pop();

        for(int j=0 ; j<G[aux].size() ; j++)
        {
            deg[j]--;
            if(deg[j]==0)
                a.push(j);
        }
    }
}