Cod sursa(job #462986)

Utilizator plastikDan George Filimon plastik Data 14 iunie 2010 12:22:26
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.38 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 
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 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] ++;
	}
	
	int *Queue  = (int*)calloc(n, sizeof(int)), u;
	a = b = 0;
	for (i = 0; i < n; ++ i)
		if (Deg[i] == 0) {
			Queue[b ++] = i;
			Used[i] = 1;
		}
	while (a < b) {
		u = Queue[a ++];
		for (i = 0; i < numNext[u]; ++ i) {
			if (Used[Next[u][i]] == 1) {
				printf("Exista ciclu: (%d %d)\n", u, Next[u][i]);
				goto end;
			}
			Deg[Next[u][i]] --;
			if (Deg[Next[u][i]] == 0) {
				Queue[b ++] = Next[u][i];
				Used[Next[u][i]] = 1;
			}
		}
		printf("%d ", u + 1);
	}
end:
	free(Queue);

	for (i = 0; i < n; ++ i)
		free(Next[i]);
	free(Next);
	free(numNext);
	free(Used);
	free(Deg);
	return 0;
}