Cod sursa(job #149818)

Utilizator alex23alexandru andronache alex23 Data 6 martie 2008 09:27:20
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <stdio.h>

 struct lista
   {int st,dr;
    lista *next;
    };

 lista *prim=new lista,*ultim=new lista,*temp;
 int v[5001],n,m,a[5001];

 int citire()
  {FILE *f;
   int x,y;

   f=fopen("sorteret.in","r");
   fscanf(f,"%d %d",&n,&m);
   fscanf(f,"%d %d",&x,&y);
   v[y]++;
   prim->st=x;
   prim->dr=y;
   prim->next=NULL;
   ultim=prim;
   for (int i=2;i<=m;i++)
    {fscanf(f,"%d %d",&x,&y);
     v[y]++;
     temp=new lista;
     temp->st=x;
     temp->dr=y;
     temp->next=NULL;
     ultim->next=temp;
     ultim=temp;
     }
   fclose(f);

   return 0;
   }

 int sortare_topologica()
  {FILE *f;
   int i,k=1,q;
   lista *t=new lista;

   f=fopen("sortaret.out","w");
   for (i=1;i<=n;i++) a[i]=v[i];
   while (k==1)
   {
   k=0;
   for (i=1;i<=n;i++)
      if (v[i]==0) {fprintf(f,"%d ",i);k=1;v[i]=-1;}
   temp=prim;t=temp;
   while (temp!=NULL)
     {q=0;
      if (v[temp->st]==-1) // stergem nodul temp
                          {q=1;
                           a[temp->dr]--;
                           if (temp==prim) {prim=temp->next;
                                            delete(temp);
                                            temp=new lista;
                                            temp=prim;
                                            t=prim;
                                            }
                                      else {t->next=temp->next;
                                            delete(temp);
                                            temp=new lista;
                                            temp=t;
                                            }

                           }
      if (q==0) {if (t!=temp) t=t->next;
                 temp=temp->next;
                 }
      }
   for (i=1;i<=n;i++) if (v[i]!=-1) v[i]=a[i];
   }

   fclose(f);
   return 0;
   }


 int main()
  {int i;

   for (i=1;i<=n;i++) v[i]=0;
   citire();
   sortare_topologica();

   /*
   temp=prim;
   while (temp!=NULL)
    {printf("%d %d\n",temp->st,temp->dr);
     temp=temp->next;
     }
   getch();  */
   return 0;
   }