Cod sursa(job #1221727)

Utilizator pentrusandaPentru Sanda pentrusanda Data 21 august 2014 12:59:43
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>

using namespace std;

struct nod
{
    int urm;
    nod *adr;
};

typedef nod *lda1;

lda1 lda[50005];

int n,m,x,y,nr[50005],sortat[50005];

int main()
{
    ifstream in ("sortaret.in");
    ofstream out ("sortaret.out");


    in>>n>>m;

    for (int i=1;i<=m;++i)
    {
        in>>x>>y;
        lda1 p=new nod;
        p->urm=y;
        p->adr=lda[x];
        lda[x]=p;
        nr[y]++;
    }

    for (int i=1;i<=n;++i) if (nr[i]==0) ++sortat[0],sortat[sortat[0]]=i;


    int i=1;
    while (i<=n)
    {
        for (lda1 p=lda[sortat[i]];p!=0;p=p->adr)
        {
            --nr[p->urm];
            if (nr[p->urm]==0) ++sortat[0],sortat[sortat[0]]=p->urm;
        }
        ++i;
    }

    for (int i=1;i<=n;++i) out<<sortat[i]<<" ";

    in.close();
    out.close();
    return 0;
}