Cod sursa(job #144809)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 27 februarie 2008 23:22:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>

int n, m, suc[50005], nr, sol[50005];

typedef struct nod
{
   int x;
   nod * a;
} *pNod;

pNod v[50005];

void citire()
{
   freopen("sortaret.in","r",stdin);
   freopen("sortaret.out","w",stdout);

   scanf("%d %d",&n,&m);
   int i, x, y;
   pNod p;
   for (i = 1; i <= m; i++)
   {
      scanf("%d %d",&x, &y);
      p = new nod;
      p -> x = x;
      p -> a = v[y];
      v[y] = p;
	  suc[x]++;
   }
}


int main()
{
   citire();
   int i, ok;
   pNod p;
   ok = 1;
   while (ok)
   {
	   ok = 0;
	   for (i = 1; i <= n; i++)
		   if (!suc[i])
		   {
			   sol[++nr] = i;
			   for (p = v[i]; p != NULL; p = p -> a) suc[p ->x]--;
			   suc[i]--;
			   ok = 1;
		   }
   }
   for (i = nr; i >= 1; i--) printf("%d ",sol[i]);
   return 0;
}