Cod sursa(job #153136)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 10 martie 2008 10:28:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream.h>
#include <fstream.h>

#define IN "sortaret.in"
#define OUT "sortaret.out"
#define maxx 100000

ifstream fin(IN);
ofstream fout(OUT);

int n,m;
struct lista
{
 int nod;
 lista *urm;
}*g[maxx];
int u[maxx];
int st[maxx];
int nst;

void citire();
void add(int x,int y);
void df(int nod);

void afis()
{
 int i;
 lista *q;

 for(i=1;i<=n;i++)
 {
  q=g[i];
  fout<<i<<"   ";
  while(q)
  {
   fout<<q->nod<<" ";
   q=q->urm;
  }
  fout<<endl;
 }
 
 fout<<endl<<endl;
 
 for(i=n-1;i>=0;i--)
  fout<<st[i]<<" ";
}

int main()
{
 int i;   
 
 citire();
  fin.close();

 for(i=1;i<=n;i++)
  if(!u[i])
   df(i);
   
// afis();

 for(i=n-1;i>=0;i--)
  fout<<st[i]<<" ";
 fout<<endl;
  
  fout.close();
return 0;
}

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

 fin>>n>>m;

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

void add(int x,int y)
{
 lista *q;

 q=new lista;

  q->nod=y;
  q->urm=g[x];
  g[x]=q;
}

void df(int nod)
{
 lista *p;

 u[nod]=1;
 
 for(p=g[nod];p!=NULL;p=p->urm)
  if(!u[p->nod])
   df(p->nod);
   
 st[nst++]=nod;  
}