Cod sursa(job #1324511)

Utilizator firutibogdanFiruti Bogdan-Cristian firutibogdan Data 22 ianuarie 2015 14:53:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<fstream>
using namespace std;
struct nod
{
    int x;
    nod *leg;
};
nod *first,*last,*q,*p,*v[50001];
int d[50001],n,m,i,x,y;
int main()
{
     ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        d[i]=0;
        v[i]=0;
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        d[y]++;
        p=new nod;
        p->x=y;
        p->leg=v[x];
        v[x]=p;
    }
    first=0;
    last=0;
    for(i=1;i<=n;i++)
    {
        if(d[i]==0)
        {
           p=new nod;
           p->x=i;
           p->leg=0;
           if(first==0)
           {
                first=p;
                last=p;
           }
           else
           {
               last->leg=p;
               last=p;
           }
        }
    }
    while(first!=0)
    {
        x=first->x;
        fout<<x<<" ";
        for(p=v[x];p!=0;p=p->leg)
        {
            d[p->x]--;
            if(d[p->x]==0)
            {
                q=new nod;
                q->x=p->x;
                q->leg=0;
                last->leg=q;
                last=q;
            }
        }
        p=first;
        first=first->leg;
        delete p;
    }
    fout.close();
    fin.close();
    return 0;
}