Cod sursa(job #757275)

Utilizator igsifvevc avb igsi Data 11 iunie 2012 18:00:46
Problema Sortare topologica Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.22 kb
#include <stdio.h>
#include <stdlib.h>

struct list
{
	int info;
	struct list *next;
};
typedef struct list List;

List *graph[50001], *stack, *solution;
int m, n, visited[50001];

void df(int current)
{
	List *temp, *neighbour;
	visited[current] = 1;
	for(neighbour = graph[current]; neighbour; neighbour = neighbour->next)
		if(!visited[neighbour->info])
		{
			temp = malloc(sizeof(List));
			temp->info = neighbour->info;
			temp->next = stack;
			stack = temp;
			
			df(neighbour->info);
			
			temp = malloc(sizeof(List));
			temp->info = stack->info;
			temp->next = solution;
			solution = temp;
			stack = stack->next;
		}
}

int main()
{
	FILE *in = fopen("sortaret.in", "r");
	FILE *out = fopen("sortaret.out", "w");
	int i, a, b;
	List *temp;
	
	fscanf(in, "%d %d", &n, &m);
	for(i = 0; i < m; i++)
	{
		fscanf(in, "%d %d", &a, &b);
		temp = malloc(sizeof(List));
		temp->info = b;
		temp->next = graph[a];
		graph[a] = temp;
	}
	
	for(i = 1; i < n; i++)
		if(!visited[i])
		{
			df(i);
			temp = malloc(sizeof(List));
			temp->info = i;
			temp->next = solution;
			solution = temp;
		}
	
	for(; solution; solution = solution->next)
		fprintf(out, "%d ", solution->info);
	fprintf(out, "\n");
	
	fclose(in);
	fclose(out);
	return 0;
}