Cod sursa(job #503782)

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

void explorare(long a[50][50],long n,long p[50],long c[50],long d[50],long f[50],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;}