Cod sursa(job #2469085)

Utilizator hunting_dogIrimia Alex hunting_dog Data 6 octombrie 2019 15:06:31
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

struct graf
    {
        int e;
        graf* urm=NULL;
    }*pr[50001],*ult[50001];

void push(graf *(&pr),graf *(&ult),int x)
{
    graf *e=new graf;
    e->e=x;
    if(!pr)
        pr=e;
    else
        ult->urm=e;
    ult=e;
}

int pop(graf *(&pr),graf *(&ult))
{
    int x=pr->e;
    pr=pr->urm;
    return x;
}

int main()
{
    int n,m,v[50001]={0};
    f>>n>>m;
    for(int i=1;i<=n;++i)
        pr[i]=ult[i]=NULL;
    while(m--)
    {
        int x,y;
        f>>x>>y;
        v[y]=x;
        push(pr[x],ult[x],y);
    }
    int p;
    for(int i=1;i<=n;++i)
        if(!v[i])
    {
        p=i;
        v[i]=0;
    }
    graf *e=NULL,*t=NULL;
    push(e,t,p);
    while(e)
    {
        v[p]=1;
        int x=pop(e,t);
        g<<x<<' ';
        while(!pr[p] && p<=n && v[p])
            ++p;
        while(pr[p])
        {
            push(e,t,pop(pr[p],ult[p]));
        }

    }

    return 0;
}