Cod sursa(job #2943688)

Utilizator andreibazavanAndrei Bazavan andreibazavan Data 21 noiembrie 2022 15:38:50
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector <int>v[50005];
int n,m,grd[50005],rez[50005];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {int a, b;
        fin>>a>>b;
        v[a].push_back(b);
        grd[b]++;
    }
    int contor=0;
    for(int i=1;i<=n;++i)
    {
        if(!grd[i])rez[++contor]=i;
    }
    int p=1, u=contor;
    while(p<=u)
    {
        int x=rez[p];
        for(auto i=v[x].begin(); i<v[x].end();++i)
        {
            grd[*i]--;
            if(grd[*i]==0)
            {
                ++u;
                rez[++contor]=*i;
            }
        }++p;
    }
    for(int i=1;i<=contor;++i)
        fout<<rez[i]<<' ';
    return 0;
}