Cod sursa(job #149560)

Utilizator thestickTudor A thestick Data 5 martie 2008 20:59:16
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <malloc.h>

long n;
long *x[50000],l[50000],s[50000],ts=0,ls=0,viz[50000];

void push(long val)
{
s[ts]=val;
ts++;
}

long get()
{
ls++;
return s[ls-1];
}

void cit()
{
long i,j,s,d,m;
FILE *f;
f=fopen("sortaret.in","r");
fscanf(f,"%d %d",&n,&m);

for(i=0;i<m;i++)
	{
		fscanf(f,"%d %*d",&s);
		l[s]++;
	}

fclose(f);

for(i=1;i<=n;i++)
{
x[i]=malloc(sizeof(long)*l[i]);
l[i]=0;
}

f=fopen("sortaret.in","r");
fscanf(f,"%*d %*d");
for(i=0;i<m;i++)
	{
	fscanf(f,"%d %d",&s,&d);
	x[s][l[s]]=d;
	l[s]++;
	}
}

void tip()
{
long i,j;
for(i=1;i<=n;i++)
        {
        printf("%d : ",i);
        for(j=0;j<l[i];j++)
        printf("%d ",x[i][j]);
        printf("\n");
        }
}

void df(long sp)
{
long cn,i;
while(ls!=ts)
{
cn=get();
viz[cn]=1;
for(i=0;i<l[cn];i++)
if(!viz[x[cn][i]])push(x[cn][i]);
}

}

void outf()
{
FILE *f;
f=fopen("sortaret.out","w");
long i;
for(i=0;i<n-1;i++)
fprintf(f,"%d ",s[i]);
fprintf(f,"%d\n",s[n-1]);
fclose(f);
}

long main()
{
long i;
cit();
for(i=1;i<=n;i++)
if(!viz[i])
{
push(i);
df(i);
}
//tip();
outf();
return 0;
}