Cod sursa(job #279597)

Utilizator andrabAndra B andrab Data 12 martie 2009 21:27:09
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream.h>
#define max 50000


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

int n,m,v[max],s[max],k;
struct nod {int info;
	    nod *urm;
	    };
nod *l[max];

void adauga(int x,int y)
{nod *c;
 c=new nod;
 c->info=x;
 c->urm=l[y];
 l[y]=c;
 }

void citire()
{int i,x,y;

 fin>>n>>m;
 for(i=1;i<=m;i++)
 {fin>>x>>y;
  adauga(y,x);
  }

 }


void df(int i)
{
 nod *c=l[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--)
 fout<<s[i]<<" ";

 fin.close();
 fout.close();

 return 0;
 }