Cod sursa(job #233195)

Utilizator k_ounu_eddyIacob Eduard k_ounu_eddy Data 17 decembrie 2008 01:26:47
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 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];

if(aux!=Sfarsit)
  while(nivel)
    {
    aux=ListaFii[nivel];
    if(aux!=Sfarsit)
      while(s[aux->info] && aux->nod_urm!=Sfarsit)
        aux=aux->nod_urm;
    if(aux->nod_urm!=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;
      }
  }
else
  {
  nod *aux2=new nod;
  aux2->info=stiva[nivel];
  aux2->nod_urm=Sortare;
  Sortare=aux2;
  }

}

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;
}