Cod sursa(job #504025)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 26 noiembrie 2010 14:23:06
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 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,u[NR];

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 u[NR])
{long j;
d[u[i]]=(*t)++;
c[u[i]]=1;
for(j=1;j<=n;j++)
if(a[u[i]][u[j]]==1&&c[u[j]]==0)
       {p[u[j]]=u[i];
       explorare(a,n,p,c,d,f,t,j,u);}
c[u[i]]=2;
f[u[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[u[i]][u[j]]=0;}
for(k=1;k<=m;k++)
       {scanf("%ld %ld",&u[i],&u[j]);
       a[u[i]][u[j]]=1;}
for(i=1;i<=n;i++)
       {v[u[i]]=i;
       c[u[i]]=0;
       p[u[i]]=0;}
for(i=1;i<=n;i++)
if(c[u[i]]==0)
       explorare(a,n,p,c,d,f,&t,i,u);
for(i=1;i<n;i++)
       {for(j=i+1;j<=n;j++)
       if(f[u[i]]<f[u[j]])
                {x=f[u[i]];
                f[u[i]]=f[u[j]];
                f[u[j]]=x;
                y=v[u[i]];
                v[u[i]]=v[u[j]];
                v[u[j]]=y;}}
for(i=1;i<=n;i++)
       printf("%ld ",v[u[i]]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;}