Pagini recente » Cod sursa (job #1084749) | Cod sursa (job #848776) | Cod sursa (job #998512) | Cod sursa (job #2401459) | Cod sursa (job #2115551)
#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);
int l[n+1][n+1], a, b; // risipa de memorie
struct nod graf[n+1];
int i, j, timp=1, stiva[n+1], rez[n+1], st =0, ok=0, index=0;
for(i=1;i<n+1;i++)
l[i][0]=1;
for(i=0; i<m; i++)
{
fscanf(f, "%d %d", &a, &b);
l[a][l[a][0]++] =b;
}
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)
{
if(graf[stiva[st]].stare == nevizitat)
{
graf[stiva[st]].stare = vizitat;
graf[stiva[st]].descoperit = timp++;
graf[stiva[st]].parinte = 0;
}
ok=0;
for(j=1; j<l[stiva[st]][0]; j++)
if(graf[l[stiva[st]][j]].stare == nevizitat )
{
a = l[stiva[st]][j];
stiva[++st] = a;
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=index-1;i>=0;i--)
fprintf(g, "%d ", rez[i]);
fclose(f);
fclose(g);
return 0;
}