Pagini recente » Cod sursa (job #32160) | Cod sursa (job #2871063) | Cod sursa (job #2377345) | Cod sursa (job #2573470) | Cod sursa (job #2115509)
#include <stdio.h>
#include <stdlib.h>
#define nevizitat 0
#define vizitat 1
#define terminat 2
struct nod
{
int descoperit;
int finalizat;
int parinte;
int stare;
};
struct muchie
{
int n1;
int n2;
};
int main()
{
int n,m;
FILE *f = fopen("sortaret.in", "r");
FILE *g = fopen("sortaret.out", "w");
fscanf(f, "%d %d", &n, &m);
struct muchie l[m];
struct nod graf[n];
int i, j, timp=1, stiva[n], rez[n], st =0, ok=0, index=0;
for(i=0; i<m; i++)
fscanf(f, "%d %d", &l[i].n1, &l[i].n2);
for(i=1; i<=n; i++)
graf[i].stare = nevizitat;
for(i=1; i<=n; i++)
{
if(graf[i].stare == nevizitat)
{
stiva[++st] = i;
while (st>0)
{
//printf("st=%d i=%d timp=%d\n", st, i,timp );
if(graf[stiva[st]].stare == nevizitat)
{
graf[stiva[st]].stare = vizitat;
graf[stiva[st]].descoperit = timp++;
graf[stiva[st]].parinte = 0;
//printf("%d ", stiva[st]);
}
ok=0;
for(j=0; j<m;j++)
if(l[j].n1 == stiva[st] && graf[l[j].n2].stare == nevizitat )
{
stiva[++st] = l[j].n2;
ok=1;
break;
}
if(ok==0)
{
graf[stiva[st]].stare = terminat;
graf[stiva[st]].finalizat = timp++;
rez[index++] = stiva[st];
if(st > 1)
graf[stiva[st]].parinte = stiva[st];
st--;
}
}
}
}
//for(i=1; i<=n; i++)
//{
// printf("i=%d %d/%d\n", i, graf[i].descoperit, graf[i].finalizat);
//}
//printf("Sortarea topologica: ");
for(i=index-1;i>=0;i--)
fprintf(g, "%d ", rez[i]);
fclose(f);
fclose(g);
return 0;
}