Cod sursa(job #2681310)

Utilizator aeliusdincaaelius dinca aeliusdinca Data 5 decembrie 2020 11:30:25
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector<int> v[50002];
int q[50002],gr[50002];
int main()
{
    int i,k,n,m,a,b;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>a>>b;
        v[a].push_back(b);
        gr[b]++;
    }
    for(k=1;k<=n;k++)
    {
        if(gr[k]==0)
                q[++q[0]]=k;
    }
    vector<int>::iterator it;
    for(i=1;i<=n;i++)
    {
        k=q[i];
        for(it=v[k].begin();it!=v[k].end();it++)
        {
            gr[*it]--;
            if(gr[*it]==0)
                q[++q[0]]=*it;
        }
    }
    for(i=1;i<=n;i++)
        out<<q[i]<<' ';
    return 0;
}