Cod sursa(job #149477)

Utilizator crusRus Cristian crus Data 5 martie 2008 19:31:19
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>
#include <stdlib.h>
#define input "sortaret.in"
#define output "sortaret.out"
#define nmax 50001
typedef struct
	{
	 long nr;
	 struct nod *urm;
	} nod;
nod *cap[nmax];
long i,n,m,x,y,gr[nmax];
void add(long x,long y)
{
 nod *q=(nod*)malloc(sizeof(nod));
 q->nr=y;
 q->urm=cap[x];
 cap[x]=q;
 gr[y]++;
}
void citire()
{
 freopen(input,"r",stdin);
 scanf("%ld %ld",&n,&m);
 for (i=1;i<=n;i++) cap[i]=NULL;
 for (i=1;i<=m;i++)
     {
      scanf("%ld %ld",&x,&y);
      add(x,y);
     }
}
void push_back(nod **cap,long nr)
{
 nod *q=(nod*)malloc(sizeof(nod));
 q->nr=nr;
 q->urm=*cap;
 *cap=q;
}
void solve()
{
 nod *head=NULL,*q;
 long i,val;
 for (i=1;i<=n;i++)
     if (!gr[i]) push_back(&head,i);
 while (head)
       {
	printf("%d ",head->nr);
	val=head->nr;
	q=head;
	head=head->urm;
	free(q);
	q=cap[val];
	while (q)
	      {
	       gr[q->nr]--;
	       if (!gr[q->nr]) push_back(&head,q->nr);
	       q=q->urm;
	      }
       }
}
int main()
{
 citire();
 freopen(output,"w",stdout);
 solve();
 return 0;
}