Nu aveti permisiuni pentru a descarca fisierul grader_test1.ok

Cod sursa(job #144164)

Utilizator TabaraTabara Mihai Tabara Data 27 februarie 2008 11:57:57
Problema Sortare topologica Scor Ascuns
Compilator cpp Status done
Runda Marime 1.4 kb
/*
    Se dau N activitati si M reguli de forma (i,j) cu semnificatia activitatea i precede activitatea j. Sa se stabileasca
  o ordine de indeplinire a activitatilor astfel incat sa fie respectate regulile date. Se considera graful activitatilor
  ca fiind aciclic.
    Complexitate: O(M+N)
*/

#include <stdio.h>

#define infile "sortaret.in"
#define outfile "sortaret.out"
#define NMAX 50005
struct NOD{int x; NOD *adr;};
FILE *fin,*fout;
NOD *prim[NMAX];
int timpfinal[NMAX],timp;
int n,m;
int ordine[NMAX];
short int vizitat[NMAX];

inline void adaug_st(NOD *(&prim), int x)
  {NOD *a=new NOD;
   a->x=x;
   a->adr=prim;
   prim=a;}

void citire()
  {
   int i,u,v;
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d",&n,&m);
   for(i=0;i<n;i++)
      prim[i]=NULL;
   for(i=0;i<m;i++)
      {fscanf(fin,"%d %d",&u,&v);
       adaug_st(prim[u-1],v-1);}
   fclose(fin);
  }

void df(int varf)
  {
   NOD *b=prim[varf];
   while(b)
       {if(!vizitat[b->x])
          {vizitat[b->x]=1;
           df(b->x);
           timp++;}
        b=b->adr;}
   timpfinal[varf]=timp;
  }

void scriere()
  {
   fout=fopen(outfile,"w");
   for(int i=0;i<n;i++)
      fprintf(fout,"%d ",ordine[i]+1);
   fclose(fout);
  }


int main()
{
int i;
citire();
timp=0;
for(i=0;i<n;i++)
   vizitat[i]=0;
for(i=0;i<n;i++)
   if(!vizitat[i])
     {vizitat[i]=1;
      df(i);
      timp++;}
for(i=0;i<n;i++)
   ordine[n-1-timpfinal[i]]=i;
scriere();
return 0;
}