Cod sursa(job #280613)

Utilizator AnaAnaBozeanu Ana AnaAna Data 13 martie 2009 14:49:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream.h>   
#define max 50005   
  
  
ifstream f("sortaret.in");   
ofstream g("sortaret.out");   
  
int n,m,v[max],s[max],k;   
struct nod {int info;   
        nod *urm;   
        };   
nod *r[max];   
  
void adauga(int x,int y)   
{nod *c;   
 c=new nod;   
 c->info=x;   
 c->urm=r[y];   
 r[y]=c;   
 }   
  
void citire()   
{int i,x,y;   
  
 f>>n>>m;   
 for(i=1;i<=m;i++)   
 {f>>x>>y;   
  adauga(y,x);   
  }   
  
 }   
  
  
void df(int i)   
{   
 nod *c=r[i];   
 v[i]=1;   
 while(c)   
 {if(v[c->info]==0) df(c->info);   
  c=c->urm;   
  }   
  
 s[++k]=i;   
 }   
  
int main()   
{int i;   
 citire();   
  
 for(i=1;i<=n;i++)   
 if(v[i]==0) df(i);   
  
 for(i=n;i>=1;i--)   
 g<<s[i]<<" ";   
  
 f.close();   
 g.close();   
  
 return 0;   
 }