Cod sursa(job #504160)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 26 noiembrie 2010 19:57:06
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include<stdio.h>
#define NR 500000
long n,i,j,k,m,p[NR],c[NR],t=0,v[NR],d[NR],f[NR],x,y,u,w,a1[NR]={0},a2[NR]={0},l,r;

void explorare(long a1[NR],long a2[NR],long n,long p[NR],long c[NR],long d[NR],long f[NR],long *t,long i,int m)
{long j;
d[i]=(*t)++;
c[i]=1;
for(r=1;r<=m;r++)
if(a1[r]==i)
       {for(j=1;j<=n;j++)
       if(a2[r]==v[j]&&c[v[j]]==0)
                {p[v[j]]=i;
                explorare(a1,a2,n,p,c,d,f,t,v[j],m);}}
c[i]=2;
f[i]=(*t)++;}

int main()
{freopen("sortaret.in","rt",stdin);
freopen("sortaret.out","wt",stdout);
scanf("%ld %ld",&n,&m);
for(k=1;k<=m;k++)
       scanf("%ld %ld",&a1[k],&a2[k]);
l=m;
for(i=1;i<l;i++)
       {for(j=i+1;j<=l;j++)
       if(a1[i]==a1[j]&&a2[i]==a2[j])
                {for(r=j;r<l;r++)
                       {a1[r]=a1[r+1];
                       a2[r]=a2[r+1];}
                l--;}}
k=1;
for(i=1;i<=l;i++)
       {w=0;
       u=0;
       for(j=1;j<k;j++)
       if(a1[i]!=v[j])
             w++;
       if(w==k-1)
             v[k++]=a1[i];
       for(r=1;r<k;r++)
       if(a2[i]!=v[r])
             u++;
       if(u==k-1)
             v[k++]=a2[i];}
for(i=1;i<=n;i++)
       {r=0;
       for(j=1;j<k;j++)
       if(v[j]!=i)
                r++;
       if(r==k-1)
                v[k++]=i;}
for(i=1;i<=n;i++)
       {c[v[i]]=0;
       p[v[i]]=0;}
for(i=1;i<=n;i++)
if(c[v[i]]==0)
       explorare(a1,a2,k,p,c,d,f,&t,v[i],l);
for(i=1;i<n;i++)
       {for(j=i+1;j<=n;j++)
       if(f[v[i]]<f[v[j]])
                {x=f[v[i]];
                f[v[i]]=f[v[j]];
                f[v[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;}