Cod sursa(job #159966)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 14 martie 2008 16:20:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
FILE*fin=fopen("sortaret.in","r");
FILE*fout=fopen("sortaret.out","w");
struct nod{int inf;nod*urm;};
#define maxn 50001
nod *vec[maxn],*q;
int grad[maxn],rez[maxn],d[maxn],n,m;
int main()
{
  int i,x,y,e,dr,b;
  fscanf(fin,"%d%d",&n,&m);
  for(i=1;i<=n;i++)
  {
    grad[i]=0;
    vec[i]=NULL;
  }
  for(i=1;i<=m;i++)
  {
    fscanf(fin,"%d%d",&x,&y);
    grad[y]++;
    q=new nod;
    q->inf=y;
    q->urm=vec[x];
    vec[x]=q;
  }
  fclose(fin);
  e=0;dr=0;b=1;
  for(i=1;i<=n;i++)
    if(grad[i]==0)
    {
      e++;
      d[e]=i;
    }
  while(b<=e)
  {
    dr++;
    rez[dr]=d[b];
    q=vec[d[b]];
    while(q)
    {
      grad[q->inf]--;
      if(grad[q->inf]==0)
      {
	e++;
	d[e]=q->inf;
      }
      q=q->urm;
    }
    b++;
  }
  for(i=1;i<=n;i++)
    fprintf(fout,"%d%c",rez[i],' ');
  fclose(fout);
  return 0;
}