Cod sursa(job #539227)

Utilizator cristian.utaUta Cristian cristian.uta Data 22 februarie 2011 17:46:49
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include<stdio.h>

FILE* in;
FILE* out;

void citire(bool** &mat, int &n)
{
	in = fopen("sortaret.in","r");
	out = fopen("sortaret.out","w");
	
	int m;
	fscanf(in,"%d%d",&n,&m);

	mat = new bool *[n];
	for (int i = 0 ; i < n ; i++)
		mat[i] = new bool [n];
	
	for (int i = 0 ; i < n ; i++)
		for (int j = 0 ; j < n ; j++)
			mat[i][j]=false;

	int x,y;
	for (int i = 0 ; i < m ; i++)
		{
			fscanf(in,"%d%d",&x,&y);
			mat[x-1][y-1]=true;
		}
}

void tSort(bool** mat, int n)
{
	int* coada;
	int* rez;
	rez = new int [n];
	coada = new int [n];
	int in=0,sf=0,m=0;
	coada = new int [n];
		for ( int i = 0 ; i < n ; i++ )
		{
			bool gasit = false;
			for ( int j = 0 ; j < n ; j++ )
				if ( mat[j][i] ) {gasit = true; break;}
			if ( gasit == false ) coada[sf++]=i;
		}
	//	for ( int i = 0 ; i < k ; i++ )
	//		fprintf(out,"%d",coada[i]);
		while ( in < sf )
		{
			rez[m] = coada[in++];
				for ( int i = 0 ; i < n ; i++ )
					if ( mat[rez[m]][i] ) 
					{
						mat[rez[m]][i]=false;
						bool gasit = false;
						for ( int j = 0 ; j < n ; j++ )
							if ( mat[j][i] ) {gasit = true; break;}
						if ( gasit == false ) coada[sf++] = i;
					}
			m++;
		}

		for ( int i = 0 ; i < m ; i++ )
			fprintf(out,"%d ",rez[i] + 1);
}

void afisare(bool** mat, int n)
{
	for (int i = 0 ; i < n ; i++)
	{
		for (int j = 0 ; j < n ; j++)
			fprintf(out,"%d ",mat[i][j]?1:0);
		fprintf(out,"\n");
	}
}

int main()
{
	int n;
	bool **mat;
	citire(mat,n);
	//afisare(mat,n);
	tSort(mat,n);

	fclose(in);
	fclose(out);

	return 0;
}