Cod sursa(job #170916)

Utilizator alle_forever13Alexandra Retegan alle_forever13 Data 3 aprilie 2008 14:54:07
Problema Sortare topologica Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<stdio.h>

#define input "sortaret.in"
#define output "sortaret.out"

#define dim 101

int n, m, nr, postordine[dim], s[dim], a[dim][dim];

void citire();
void dfs(int k);

FILE *in, *out;

int main()
{
	in = fopen (input, "r");
	out = fopen (output, "w");

	citire();

	int i;

	for(i=1; i<=n; i++)

		if(!s[i])

			dfs(i);

	for(i=n; i; i--)

		fprintf(out, "%d ", postordine[i]);

	fprintf(out, "\n");

	return 0;

}

void citire()
{
	int i, x, y;

	fscanf(in, "%d%d", &n, &m);

	for(i=1; i<=m; i++)
	{
		fscanf(in, "%d%d", &x, &y);

		a[x][0]++;
		a[x][a[x][0]]=y;

	}

}

void dfs(int k)
{
	int i;

	s[k] = 1;

	for(i=1; i<=a[k][0]; i++)

		if(!s[a[k][i]])

			dfs(a[k][i]);

	postordine[++nr]=k;
}