Cod sursa(job #259759)

Utilizator DjSefuWrong name DjSefu Data 15 februarie 2009 19:54:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<stdio.h>
FILE *f=fopen("sortaret.in","r"),
     *g=fopen("sortaret.out","w");
#define R_MAX 100005
#define N_MAX 50005
struct nod
{ int v;
  nod *next;
}
typedef nod,*pnod;
pnod l[N_MAX];
int n,i,j,m,k,grade[N_MAX],coada[N_MAX],kr,x,y;
void add(int x,int y)
{ pnod p=new nod;
  p->next=l[x];
  p->v=y;
  l[x]=p;
  ++grade[y];
}
void write()
{ 
  for(int i=1;i<=n;++i) fprintf(g,"%d ",coada[i]);
}
void solve()
{ int i,x;
  for(i=1;i<=n;++i) if(grade[i]==0) coada[++coada[0]]=i;
  for(i=1;i<=n;++i)
  {
    x=coada[i];
    for(pnod p=l[x];p;p=p->next){ --grade[p->v];
                                  if(grade[p->v]==0) { coada[++coada[0]]=p->v;
                                                       }
                                                       }
}                                               
 write();
}
int main()
{ fscanf(f,"%d %d",&n,&m);
  for(i=1;i<=m;++i) { fscanf(f,"%d %d",&x,&y);add(x,y);}
  solve();
  fclose(f);
  fclose(g);
  return 0;
}