Cod sursa(job #784195)

Utilizator f.v.antonFlavius Anton f.v.anton Data 5 septembrie 2012 01:57:13
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.26 kb
#include <stdio.h>
#include <stdlib.h>

void read(FILE *f, int ***a, int **deg, int *n, int *m)
{
	int i, x, y;
	fscanf(f, "%d %d", n, m);
	*a = calloc(*n + 1, sizeof(int*));

	for (i = 0; i < *n+1; i++)
		(*a)[i] = calloc(*n + 1, sizeof(int));

	*deg = calloc(*n + 1, sizeof(int));

	for (i = 1; i <= *m; i++) {
		fscanf(f, "%d %d", &x, &y);
		(*a)[x][y]++;
		(*deg)[y]++;
	}
}

int* toposort(int **a, int *deg, int n)
{
	int i, vcount = 0, node, *v = NULL;
	int qstart = 0, qend = 0, *q = calloc(n + 5, sizeof(int));

	for (i = 1; i <= n; i++)
		if (deg[i] == 0) {
			q[qstart] = i;
			qend++;
		}

	v = calloc(n + 1, sizeof(int));

	while (qend > qstart) {
		node = q[qstart];
		qstart++;
		v[vcount++] = node;

		for (i = 1; i <= n; i++)
			if (a[node][i] > 0) {
				a[node][i]--;
				deg[i]--;
				if (deg[i] == 0) {
					q[qend] = i;
					qend++;
				}
			}
	}
	free(q);
	return v;
}

void print(FILE *g, int *v, int n)
{
	int i;
	for (i = 0; i < n; i++)
		fprintf(g, "%d ", v[i]);
}

int main(void)
{
	int n, m, **a = NULL, *v = NULL, *deg = NULL;
	FILE *f, *g;
	f = fopen("sortaret.in", "rt");
	g = fopen("sortaret.out", "wt");

	read(f, &a, &deg, &n, &m);
	v = toposort(a, deg, n);

	print(g, v, n);

	fclose(f);
	fclose(g);

	/* discard(a, n); */
	free(v);
	free(deg);
	return 0;
}