Cod sursa(job #284238)

Utilizator vladbBogolin Vlad vladb Data 21 martie 2009 12:35:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<fstream>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

struct nod { int v;
             nod *next;
           } *v[50001],*list; 
long n,m;
int c[50001];

void citire()
{    long i,x,y;
     nod *p;
     fin>>n>>m;
     for(i=1;i<=m;i++)
     {      fin>>x>>y;
            p=new nod;
            p->v=y;
            p->next=v[x];
            v[x]=p;
     }
}

void df(int nd)
{    nod *p,*q;
     c[nd]=1;
     p=v[nd];
     while(p!=NULL)
     {     if(c[p->v]==0)
              df(p->v);
           p=p->next;
     }
     c[nd]=2;
     q=new nod;
     q->v=nd;
     q->next=list;
     list=q;
}           
     

void sorttop()
{    int i;
     for(i=1;i<=n;i++)
        if(c[i]==0)
           df(i);
}

void afis()
{    nod *p;
     p=list;
     while(p!=NULL)
     {     fout<<p->v<<" ";
           p=p->next;
     }
}
 
int main()
{   citire();
    sorttop();
    afis();
    fin.close();
    fout.close();
    return 0;
}