Pagini recente » Cod sursa (job #3228934) | Cod sursa (job #23968) | Cod sursa (job #2330168) | Cod sursa (job #1276636) | Cod sursa (job #2136990)
#include <stdio.h>
#include <stdlib.h>
#define nevizitat 0
#define vizitat 1
#define terminat 2
struct nod
{
int id;
int descoperit;
int finalizat;
struct nod *parinte;
int stare;
struct lista *lista_adiacenta;
};
struct lista
{
struct nod *vecin;
struct lista *urm;
};
int main()
{
int n,m , nod1, nod2;
FILE *f = fopen("sortaret.in", "r");
FILE *g = fopen("sortaret.out", "w");
fscanf(f, "%d %d", &n, &m);
struct nod graf[n+1], *stiva[n+1], rez[n+1];
struct lista *aux;
int i, j, timp=1, st =0, ok=0, index=0;
for(i=1; i<=n; i++)
{
graf[i].id =i;
graf[i].stare = nevizitat;
graf[i].lista_adiacenta = NULL;
}
for(i=0; i<m; i++)
{
fscanf(f, "%d %d", &nod1, &nod2);
if(graf[nod1].lista_adiacenta == NULL)
{
//e primul nod din lista
graf[nod1].lista_adiacenta = (struct lista*)malloc(sizeof(struct lista));
graf[nod1].lista_adiacenta->vecin = &graf[nod2];
graf[nod1].lista_adiacenta->urm = NULL;
}
else
{
//in lista mai avem noduri
aux = graf[nod1].lista_adiacenta;
while(aux->urm != NULL)
aux = aux->urm;
aux->urm = (struct lista*)malloc(sizeof(struct lista));
aux->urm->vecin = &graf[nod2];
aux->urm->urm=NULL;
}
}
for(i=1; i<=n; i++)
{
if(graf[i].stare == nevizitat)
{
stiva[++st] = &graf[i];
while (st>0)
{
if(stiva[st]->stare == nevizitat)
{
stiva[st]->stare = vizitat;
stiva[st]->descoperit = timp++;
stiva[st]->parinte = NULL;
//printf("%d ", stiva[st]->id);
}
ok=0;
aux = stiva[st]->lista_adiacenta;
while(aux)
{
if(aux->vecin->stare == nevizitat )
{
stiva[++st] = aux->vecin;
ok=1;
break;
}
aux = aux->urm;
}
if(ok==0)
{
stiva[st]->stare = terminat;
stiva[st]->finalizat = timp++;
rez[index++] = (*stiva[st]);
st--;
}
}
}
}
for(i=index-1;i>=0;i--)
fprintf( g,"%d ", rez[i].id);
fclose(f);
fclose(g);
return 0;
}