Cod sursa(job #462997)

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

#include <stdio.h>
#include <stdlib.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 color) {
	Used[a] = color;
	int i;
	for (i = 0; i < numNext[a]; ++ i) {
		if (!Used[Next[a][i]])
			depthFirst(Next[a][i], color);
	}
	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));
	int color = 1;
	for (i = 0; i < m; ++ i)
		if (Deg[i] == 0)
			depthFirst(i, color ++);

	for (i = n - 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;
}