Cod sursa(job #2390468)

Utilizator BadulescuCatalinBadulescu Andrei Catalin BadulescuCatalin Data 28 martie 2019 09:14:59
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>
using namespace std;

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

long long i,m,n,x,y,deg[50100],q[50100];
vector <int> g[50100];
vector<int>::iterator it;

int main()
{

    fin>>n>>m;
    for(i=1;i<=m;++i)
        {
            fin>>x>>y;
            g[x].push_back(y);
            deg[y]++;
        }

    for(i=1;i<=n;++i)
        if(deg[i]==0)
        q[++q[0]]=i;
    for(i=1;i<=n;++i)
    {
        x=q[i];
         for(it = g[x].begin(); it != g[x].end(); ++it)
        {
            deg[*it]--;
            if(deg[*it] == 0) q[++q[0]] = *it;
        }

    }
    for(i=1;i<=n;++i)
        fout<<q[i]<<" ";
    return 0;
}