Cod sursa(job #463002)

Utilizator plastikDan George Filimon plastik Data 14 iunie 2010 12:46:18
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.5 kb
// http://infoarena.ro/problema/sortaret

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int **Next, // vecinii fiecarui nod
    *numNext, // numarul de vecini ai fiecarui nod
    n, m; // numarul de noduri respectiv muchii

int *Deg, // gradul fiecarui nod
    *Stack; // pun pe stiva (privita ca vector), deci stiva e invers in memorie nodurile cand le termin de parcus; e echivalent cu o sortare dupa timpii de final
char *Used; // a fost vizitat sau nu

inline void addEdge(int a, int b) {
	Next[a] = (int*)realloc(Next[a], (numNext[a] + 1) * sizeof(int));
	Next[a][numNext[a] ++] = b;
}

int numStack = 0;
void depthFirst(int a) {
	int i;
	for (i = 0; i < numNext[a]; ++ i)
		if (!Used[Next[a][i]]) {
			Used[Next[a][i]] = 1;
			depthFirst(Next[a][i]);
		}
	
	Stack[numStack ++] = a;
}

int main() {
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	scanf("%d%d", &n, &m);
	Next = (int**)calloc(n, sizeof(int*));
	numNext = (int*)calloc(n, sizeof(int));
	Deg = (int*)calloc(n, sizeof(int));
	Used = (char*)calloc(n, sizeof(char));

	int i, a, b;
	for (i = 0; i < m; ++ i) {
		scanf("%d%d", &a, &b);
		addEdge(a - 1, b - 1);
		Deg[b - 1] ++;
	}

	Stack = (int*)calloc(n, sizeof(int));
	for (i = 0; i < n; ++ i)
		if (Deg[i] == 0) {
			Used[i] = 1;
			depthFirst(i);
		}

	assert(numStack == n);

	for (i = numStack - 1; i >= 0; -- i)
		printf("%d ", Stack[i] + 1);
		
	for (i = 0; i < n; ++ i)
		free(Next[i]);
	free(Stack);
	free(Next);
	free(numNext);
	free(Used);
	free(Deg);
	return 0;
}