Cod sursa(job #2680591)

Utilizator Tudor2PopescuPopescu Tudor-Cristian Tudor2Popescu Data 3 decembrie 2020 19:10:41
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int start[50002],n,m,i,j,x,y,k,st,dr,coada[50002],gr[50002];
struct adiacent
{
    int vecin,urm;
};
adiacent L[100002];
int main()
{
     fin>>n>>m;
     for(i=1;i<=m;i++)
     {
         fin>>x>>y;
         gr[y]++;
         k++;
         L[k].vecin=y;
         L[k].urm=start[x];
         start[x]=k;
     }
     st=1;
     dr=0;
     for(i=1;i<=n;i++)
     {
         if(gr[i]==0)
         {
             dr++;
             coada[dr]=i;
         }
     }
     while(st<=dr)
     {
         for(i=start[coada[st]];i!=0;i=L[i].urm)
         {
             gr[L[i].vecin]--;
             if(gr[L[i].vecin]==0)
             {
                 dr++;
                 coada[dr]=L[i].vecin;
             }
         }
         st++;
     }
     for(i=1;i<=dr;i++)
     {
         fout<<coada[i]<<" ";
     }
     fin.close();
     fout.close();
     return 0;



}