Cod sursa(job #503783)

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

void explorare(long a[NR][NR],long n,long p[NR],long c[NR],long d[NR],long f[NR],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);
for(i=1;i<=n;i++)
       {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;}
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");
fclose(stdin);
fclose(stdout);
return 0;}