Cod sursa(job #757278)

Utilizator igsifvevc avb igsi Data 11 iunie 2012 18:10:08
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <stdlib.h>

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

List *graph[50001], *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])
			df(neighbour->info);

	temp = malloc(sizeof(List));
	temp->info = current;
	temp->next = solution;
	solution = temp;
}

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);
	
	for(; solution; solution = solution->next)
		fprintf(out, "%d ", solution->info);
	fprintf(out, "\n");
	
	fclose(in);
	fclose(out);
	return 0;
}