Cod sursa(job #475074)

Utilizator Programmer01Mierla Laurentiu Marian Programmer01 Data 5 august 2010 21:33:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<stdio.h>

struct Cell{
	int val;
	Cell *next;
};

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




void df(int x){
	viz[x] = 1;
	for(Cell *cell = a[x]; cell; cell = cell->next)
		if(!viz[cell->val]){
			df(cell->val);
		}
	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 Cell*[n+1];
	for(int i=0; i<=n; i++)
        	a[i] = NULL;

	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++){
		Cell *cell = new Cell;
		int x;
		fscanf(ifile, "%i %i", &x, &cell->val);
		cell->next = a[x];
		a[x] = cell;
		b[cell->val] = 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;
}