Cod sursa(job #2526136)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 18 ianuarie 2020 12:05:15
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
using namespace std;
const int N=50009;
const int M = 100001;
int q[N],d[N],lst[N],vf[M],n,m,L,D,nr,urm[M],nrp[N];
ifstream in("sortaret.in");
ofstream out("sortaret.out");
void adauga(int x, int y)

{

    vf[++nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
    nrp[y]++;
}
void sorttop()

{

    int st,dr;
    st=0;
    dr=-1;
    for(int i=1; i<=n; i++)
    {
        if(nrp[i]==0) q[++dr]=i;

    }

    while(st<=dr)

    {

        int x=q[st++];
        out<<x<<" ";

        for(int p=lst[x]; p!=0; p=urm[p])

        {

            int y=vf[p];
            nrp[y]--;
            if(nrp[y]==0)

            {

                q[++dr]=y;



            }

        }

    }

}



int main()

{

    in>>n>>m;
    for(int i=1; i<=m; i++)

    {
        in>>L>>D;
        adauga(L,D);

    }


    sorttop();


    return 0;

}