Cod sursa(job #1132782)

Utilizator 0x7c00Gabriel Ciubotaru 0x7c00 Data 3 martie 2014 21:50:24
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.26 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 = NULL;
			if(p == NULL)
				s = p = nod;
			else
			{
				p->next = nod;
				p  = nod;
			}
		}
	while(s!=NULL)
	{
		x = s->val;
		s = s->next;
		nod = graf[x];
		while(nod)
		{
			y = nod->val;
			nod = nod->next;
			grad[y]--;
			if(grad[y] == 0)
			{
				fprintf(g,"%d ",y);
				nod2->val = y;
				if(s == NULL)
					s = p = nod2;
				else
				{
					p->next = nod2;
					p = nod2;
				}
			}
		}
	}
	fclose(g);
}