Pagini recente » Cod sursa (job #984204) | Cod sursa (job #298626) | Cod sursa (job #1860240) | Cod sursa (job #1056105) | Cod sursa (job #233193)
Cod sursa(job #233193)
#include<stdio.h>
#include<string.h>
struct nod
{int info;
nod *nod_urm;};
nod **ListaFii,*Sfarsit,*Sortare;
int N,M,*stiva;
bool *s;
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;
s=new bool[N+1];
stiva=new int[N+1];
memset(s,0,sizeof(s)*(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)
{
if(aux!=Sfarsit)
while(s[aux->info] && aux->nod_urm!=Sfarsit)
aux=aux->nod_urm;
if(aux!=Sfarsit && s[aux->info]==0)
{s[aux->info]=1;
stiva[++nivel]=aux->info;
aux=ListaFii[aux->info];
}
else
{
nod *aux2=new nod;
aux2->info=stiva[nivel];
aux2->nod_urm=Sortare;
Sortare=aux2;
aux=ListaFii[stiva[--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;
}