Cod sursa(job #303259)

Utilizator cristiprgPrigoana Cristian cristiprg Data 9 aprilie 2009 18:08:37
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <cstdlib>
#define DIM 2000

const int INF = 1<<30;
int n, m, a[DIM][DIM], coada[DIM];

bool grad0(int j)
{
	for (int i = 1; i <= n; i++)
		if (a[i][j] == 1)
			return 0;


	return 1;
}


int main()
{
	FILE *f = fopen("sortaret.in", "r");
	fscanf(f, "%d%d", &n, &m);
	int i, j, x, y;
/*	for(i = 1; i <= n; i++)
		for (j = 1;  j <= m; j++)
			a[i][j] = 0;
*/
	for (i = 1;  i <= m; i++)
		fscanf(f, "%d%d", &x, &y), a[x][y] = 1;
	fclose(f);

/*	for(i = 1; i <= n; i++)
	{
		for (j = 1;  j <= n; j++)
			printf("%3d", a[i][j]);

		printf("\n");

	}
*/
	//caut nodurile cu grad extern 0
	int gasit, dr = 0, st = 1;
	for (j = 1; j <= n; j++)
	{
		gasit = 0;
		for (i = 1; i <= n && !gasit; i++)
			if (a[i][j] == 1)
				gasit = 1;

		if (!gasit)
			coada[++dr] = j;
	}

/*	printf("coada: ");
	for (i = 1; i <= dr; i++)
			printf("%3d", coada[i]);
*/
	f = fopen("sortaret.out", "w");
	while(st <= dr)
	{
		i = coada[st];
		fprintf(f, "%d ", i);
		for (j = 1; j <= n ; j++)
			if (a[i][j] == 1)
			{
				a[i][j] = 0;
				if (grad0 (j))
					coada[++dr] = j;
			}
		st++;
	}

	return 0;
}