Cod sursa(job #1677239)

Utilizator experiment322Alexandru-Damian Manea experiment322 Data 6 aprilie 2016 13:56:45
Problema Sortare topologica Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.02 kb
#include <stdio.h>
#include <stdlib.h>

enum {
	NMAX = 50001
};

typedef struct node {
	int val;
	struct node *next;
} node_t;

static node_t *graph[NMAX];
static int n, l, visited[NMAX], parentno[NMAX], list[NMAX];

static void Add(int a, int b)
{
	node_t *dest;
	dest = malloc(sizeof(node_t));
	dest->val = b;
	dest->next = graph[a];
	graph[a] = dest;
}

static void Read(void)
{
	int i, m, a, b;
	scanf("%i%i", &n, &m);
	for (i = 0; i < m; ++i) {
		scanf("%i%i", &a, &b);
		++parentno[b];
		Add(a, b);
	}
}

static void TopSort(int v)
{
	node_t *cn;
	cn = graph[v];
	visited[v] = 1;
	while (cn != NULL) {
		if (!visited[cn->val]) {
			TopSort(cn->val);
		}
		cn = cn->next;
	}
	fprintf(stderr, "%i ", v);
	list[l++] = v;
}

static void Print(void)
{
	int i;
	for (i = l - 1; i >= 0; --i) {
		printf("%i ", list[i]);
	}
	printf("\n");
}

int main(void)
{
	int i;
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	Read();
	for (i = 1; i <= n; ++i) {
		if (parentno[i] == 0) {
			TopSort(i);
		}
	}
	Print();
	return 0;
}