Cod sursa(job #504427)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 27 noiembrie 2010 17:40:19
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include<stdio.h>
#define NR 50001
long n,i,j,k,m,p[NR]={0},c[NR]={0},t=0,v[NR],d[NR]={0},f[NR]={0},x,y;
long a1[20001][20001],a2[20001][20001],a3[20001][20001],a4[20001][20001],a5[20001][20001];

void merge(long f[NR],long v[NR],long p,long m,long q)
{long i=p,j=m+1,ny=p,y[NR],z[NR],k;
while(i<=m&&j<=q)
         {if(f[i]<=f[j])
                   {y[ny]=f[i];
                   z[ny]=v[i];
                   ny++;
                   i++;}
         else
                   {y[ny]=f[j];
                   z[ny]=v[j];
                   ny++;
                   j++;}}
while(i<=m)
         {y[ny]=f[i];
         z[ny]=v[i];
         ny++;
         i++;}
while(j<=q)
         {y[ny]=f[j];
         z[ny]=v[j];
         ny++;
         j++;}
for(k=p;k<=q;k++)
         {f[k]=y[k];
         v[k]=z[k];}}

void mergeSort(long f[NR],long v[NR],long p,long q)
{long m=(p+q)/2;
if(p<q)
         {mergeSort(f,v,p,m);
         mergeSort(f,v,m+1,q);
         merge(f,v,p,m,q);}}

void explorare(long *t,long i)
{long j;
c[i]=1;
for(j=1;j<=n;j++)
if(c[j]==0&&(a1[i][j]==1||a2[i][j]==1||a3[i][j]==1||a4[i][j]==1||a5[i][j]==1))
        explorare(t,j);
f[i]=++(*t);}

int main()
{freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%ld %ld",&n,&m);
for(k=1;k<=m;k++)
       {scanf("%ld %ld",&i,&j);
       if(k<=20000)
              a1[i][j]=1;
       else
              if(k>20000&&k<=40000)
                       a2[i][j]=1;
              else
                       if(k>40000&&k<=60000)
                                 a3[i][j]=1;
                       else
                                 if(k>60000&&k<=80000)
                                          a4[i][j]=1;
                                 else
                                          a5[i][j]=1;}
for(i=1;i<=n;i++)
       v[i]=i;
for(i=1;i<=n;i++)
if(c[i]==0)
       explorare(&t,i);
mergeSort(f,v,1,n);
for(i=n;i>=1;i--)
       printf("%ld ",v[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;}