Cod sursa(job #478142)

Utilizator a.stanciuStanciu Adrian a.stanciu Data 17 august 2010 16:50:41
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.67 kb
#include <stdio.h>
#include <stdlib.h>

#define ALB 0
#define GRI 1
#define NEGRU 2

typedef struct Nod 
{
	int val;
	struct Nod *urm;
} Nod;

struct Nod *sol;

void init(struct Nod *list, int n)
{
	int i;
	for (i = 1; i <= n; i++)
	{
		list[i].val = ALB;
		list[i].urm = NULL;
	}
	sol = (struct Nod *)malloc(sizeof(struct Nod));
	sol->val = 0;
	sol->urm = NULL; 
}

void add(struct Nod *list, int x, int y)
{
	struct Nod *vf = (struct Nod *)malloc(sizeof(struct Nod));
	vf->val = y;
	vf->urm = NULL;
	
	struct Nod *tmp = &list[x];
	while (tmp->urm) tmp = tmp->urm;
	tmp->urm = vf;
}

void print(struct Nod *list, int n)
{
	int i;
	struct Nod *tmp;
	for (i = 1; i <= n; i++)
	{
		printf("%d: ", i);
		tmp = &list[i];
		while(tmp)
		{
			printf("%d ", tmp->val);
			tmp = tmp->urm;
		}
		printf("\n");
	}
}

void df(struct Nod *list, int x)
{
	list[x].val = GRI;

	struct Nod *tmp = &list[x];
	tmp = tmp->urm;
	while (tmp)
	{ 
		if (list[tmp->val].val == ALB) df(list, tmp->val);
		tmp = tmp->urm;
	}

	list[x].val = NEGRU;
	struct Nod *s = (struct Nod *)malloc(sizeof(struct Nod));
	s->val = x;
	s->urm = sol;
	sol = s;
}

void sortaret(struct Nod *list, int n)
{
	int i;
	for (i = 1; i <= n; i++)
		if (list[i].val == ALB) df(list, i);
}

int main()
{
	int n, m, i, x, y;
	FILE *f, *g;

	f = fopen("sortaret.in", "r");
	g = fopen("sortaret.out", "w");

	fscanf(f, "%d %d", &n, &m);
	
	struct Nod *list = (struct Nod *)malloc(sizeof(struct Nod) * (n + 1));
	init(list, n);	

	for (i = 1; i <= m; i++)
	{
		fscanf(f, "%d %d", &x, &y);
		add(list, x, y);
	}
	//print(list, n);

	sortaret(list, n);
	while(sol->urm)
	{
		fprintf(g, "%d ", sol->val);
		sol = sol->urm;
	}

	fclose(f);
	fclose(g);

	return 0;
}