Cod sursa(job #2880350)

Utilizator T1raduTaerel Radu Nicolae T1radu Data 29 martie 2022 17:14:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m,a,b,deg[50100],q[50100],t;
vector<int> G[50100];
int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        fin >> a >> b;
        G[a].push_back(b);
        deg[b]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(deg[i]==0) q[++t]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int x=q[i];
        for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it)
        {
            deg[*it]--;
            if(deg[*it]==0) q[++t]=*it;
        }
    }
    for(int i=1;i<=t;i++)
        fout << q[i] << " ";
    return 0;
}