Cod sursa(job #475051)

Utilizator Programmer01Mierla Laurentiu Marian Programmer01 Data 5 august 2010 19:53:39
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>

int **a, *b, *c, *viz, index;
int n, m;

void df(int x){
	viz[x] = 1;
	for(int i=1;i<=n;i++)
		if(!viz[i] && a[x][i]){
			df(i);
		}
	c[index++] = x;
		
}

void sort(){
	for(int i=1;i<=n;i++)
		if(!b[i]) df(i);
}


int main()
{
	FILE *ofile, *ifile;
	
	ifile = fopen("sortaret.in", "r");
	fscanf(ifile, "%i %i", &n, &m);

	a = new int*[n+1];
	for(int i=0;i<=n;i++)
		a[i] = new int[n+1];
		
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			a[i][j] = 0;


	b = new int[n+1];
	c = new int[n];
	viz = new int[n+1];
	
	for(int i=0;i<=n;i++)
		b[i] = viz[i] = 0;

	for(int i=0; i<m; i++){
		int x, y;
		fscanf(ifile, "%i %i", &x, &y);
		a[x][y] = 1;
		b[y] = 1;
	}
	
	fclose(ifile);	
	
	sort();

	ofile = fopen("sortaret.out", "w");
	
	for(int i=index-1;i>=0;i--)
	       fprintf(ofile, "%i ", c[i]);

	fclose(ofile);

	return 0;
}