Cod sursa(job #503787)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 24 noiembrie 2010 22:12:03
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
#include<stdlib.h>
#define NR 50001
long n,i,j,k,m,**a,*p,*c,t=0,*v,*d,*f,x,y;

void explorare(long **a,long n,long *p,long *c,long *d,long *f,long *t,long i)
{long j;
d[i]=(*t)++;
c[i]=1;
for(j=1;j<=n;j++)
if(a[i][j]==1&&c[j]==0)
       {p[j]=i;
       explorare(a,n,p,c,d,f,t,j);}
c[i]=2;
f[i]=(*t)++;}

int main()
{freopen("sortaret.in","rt",stdin);
freopen("sortaret.out","wt",stdout);
scanf("%ld %ld",&n,&m);
a=(long**)malloc(NR*sizeof(long*));
for(i=1;i<=n;i++)
       {a[i]=(long*)malloc(NR*sizeof(long*));
       for(j=1;j<=n;j++)
               a[i][j]=0;}
for(k=1;k<=m;k++)
       {scanf("%ld %ld",&i,&j);
       a[i][j]=1;}
v=(long*)malloc(NR*sizeof(long));
c=(long*)malloc(NR*sizeof(long));
p=(long*)malloc(NR*sizeof(long));
for(i=1;i<=n;i++)
       {v[i]=i;
       c[i]=0;
       p[i]=0;}
for(i=1;i<=n;i++)
if(c[i]==0)
       explorare(a,n,p,c,d,f,&t,i);
for(i=1;i<n;i++)
       {for(j=i+1;j<=n;j++)
       if(f[i]<f[j])
                {x=f[i];
                f[i]=f[j];
                f[j]=x;
                y=v[i];
                v[i]=v[j];
                v[j]=y;}}
for(i=1;i<=n;i++)
       printf("%ld ",v[i]);
printf("\n");
free(a);
free(v);
free(c);
free(p);
fclose(stdin);
fclose(stdout);
return 0;}