Cod sursa(job #233317)

Utilizator k_ounu_eddyIacob Eduard k_ounu_eddy Data 17 decembrie 2008 15:15:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdio.h>
#include<string.h>

struct nod
{int info;
nod *nod_urm;};
nod **ListaFii,*Sfarsit,*Sortare;

int N,M,*stiva;
bool s[50001];

void adauga(int a,int b)
{nod *aux;
aux=new nod;
aux->info=b;
aux->nod_urm=ListaFii[a];
ListaFii[a]=aux;}

inline void initializeaza()
{
FILE *pin=fopen("sortaret.in","r");
fscanf(pin,"%d",&N);
fscanf(pin,"%d",&M);

ListaFii=new nod*[N+1];
Sfarsit=new nod;
Sortare=Sfarsit;
stiva=new int[N+1];

for(int i=1;i<=N;i++)
  ListaFii[i]=Sfarsit;
int a,b;
for(;M;M--)
  {
  fscanf(pin,"%d",&a);
  fscanf(pin,"%d",&b);
  adauga(a,b);
  }
fclose(pin);
}

void df(int Nod)
{
s[Nod]=1;
int nivel=1;
stiva[nivel]=Nod;
nod *aux;
aux=ListaFii[Nod];

while(nivel)
  {
  aux=ListaFii[stiva[nivel]];
  
  if(aux!=Sfarsit)
    while(aux->nod_urm!=Sfarsit && s[aux->info])
      aux=aux->nod_urm;
      
  if(aux!=Sfarsit && s[aux->info]==0)
    {s[aux->info]=1;
    stiva[++nivel]=aux->info;}
  else
    {nod *aux2=new nod;
    aux2->info=stiva[nivel];
    aux2->nod_urm=Sortare;
    Sortare=aux2;
    --nivel;}
  }
}

inline void rezolva()
{
for(int i=1;i<=N;i++)
  if(!s[i])
    df(i);
}

inline void incheie()
{
FILE *pout=fopen("sortaret.out","w");
for(;Sortare!=Sfarsit;Sortare=Sortare->nod_urm)
  fprintf(pout,"%d ",Sortare->info);
fclose(pout);
}



int main()
{
initializeaza();
rezolva();
incheie();
return 0;
}