Cod sursa(job #1132791)

Utilizator 0x7c00Gabriel Ciubotaru 0x7c00 Data 3 martie 2014 21:59:56
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.27 kb
#define _CRT_SECURE_NO_WARNINGS
#include <malloc.h>
#include <stdio.h>
#include <string.h>
#define NAME "sortaret"
#define OPEN f = fopen(NAME".in","r");g = fopen(NAME".out","w");
FILE *f,*g;


#define MAXM 100001
#define MAXN 50001
struct _NOD;
typedef struct _NOD NOD; 

struct _NOD
{
	unsigned int val;
	NOD *next;
};


unsigned int n,m;
unsigned int grad[MAXN];
NOD * graf[MAXN];
unsigned int i,x,y;
NOD *nod,*nod2;
NOD *s;
NOD *p;
int main()
{
	OPEN;
	fscanf(f,"%d%d",&n,&m);
	for(i=0;i<m;i++)
	{
		fscanf(f,"%d%d",&x,&y);
		grad[y] ++;
		nod = (NOD *)malloc(sizeof(NOD));
		nod->val = y;
		nod->next = graf[x];
		graf[x] = nod;
	}
	s = NULL;
	p = NULL;
	for(i=1;i<=n;i++)
		if(grad[i] == 0)
		{
			fprintf(g,"%d ",i);
			nod = (NOD *)malloc(sizeof(NOD));
			nod->val = i;
			nod->next = p;
			p = nod;
		}
	s =p;
	p = NULL;
	while((s!=NULL)||(p!=NULL))
	{
		if(s == NULL)
		{
			s=p;
			p=NULL;
		}
		x = s->val;
		nod = s;
		s = s->next;
		free(nod);
		nod = graf[x];
		while(nod)
		{
			y = nod->val;
			nod2 = nod;
			nod = nod->next;
			grad[y]--;
			if(grad[y] == 0)
			{
				fprintf(g,"%d ",y);
				nod2->val = y;
				nod2->next = p;
				p = nod2;
			}
			else
				free(nod2);
		}
	}
	fclose(g);
}