Cod sursa(job #164771)

Utilizator redkar23Dezactiveazama redkar23 Data 24 martie 2008 20:03:39
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
#define MAX 50000
FILE *f,*g;
int pred[MAX];
int n,m,i,a,b,k,printed;
int c[MAX];


struct lista{
   int a;
   lista *next;
};



lista *scs[MAX];
lista *nr;


int main(){
f=fopen("sortaret.in","r");
g=fopen("sortaret.out","w");
fscanf(f,"%d %d",&n,&m);
for(i=0;i<m;i++){
  fscanf(f,"%d %d",&a,&b);
  pred[b]++;  
  nr=new lista;
  nr->next=scs[a];
  nr->a = b;
  scs[a]=nr;
  }

while(printed<n){
k=0;
for(i=1;i<=n;i++)
   if(pred[i]==0) c[k++]=i;
for(i=0;i<k;i++){
   fprintf(g,"%d\n",c[i]);
   printed++;
   pred[c[i]]=-1;
   nr=scs[c[i]];
   while(nr){
      pred[nr->a]--;
      nr=nr->next; 

      }
   }

} 
 fclose(g);
return 0;
}