Cod sursa(job #176939)

Utilizator vladcyb1Vlad Berteanu vladcyb1 Data 11 aprilie 2008 23:19:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 50001
#define MMAX 100001
#define FIN "sortaret.in"
#define FOUT "sortaret.out"

typedef struct nod {
	int info;
	struct nod * next;
} NOD;

NOD * V[NMAX], * list;

int NR[NMAX], SOL[NMAX], N, M, X, Y, k;
FILE * fin , * fout;

void push( NOD *& list, int info )
{
	NOD * q = new NOD;
	q->info = info;
	q->next = NULL;
	if( !list )
		list = q;
	else
	{
		q->next = list;
		list = q;
	}
}

int pop( NOD *& list )
{
	NOD * q;
	int info;
	if( list )
	{
		info = list->info;
		q = list;
		list = list->next;
		delete q;
		return info;
	}
	else return 0;
}

void SortTop()
{
	int i, t;
	NOD * tmp, * list = NULL;
	for( i = 1; i <= N; i++ )
		if( !NR[i] )
			push( list, i );
	while( t = pop( list) )
	{
		tmp = V[t];
		while( tmp != NULL )
		{
			NR[tmp->info]--;
			if( !NR[tmp->info] ) 
				push( list, tmp->info );
			tmp = tmp->next;
		}
		SOL[k++] = t;
	}
	for( i = k - 1; i >= 0; i-- )
		fprintf( fout, "%d ", SOL[i]);
	fprintf( fout, "\n");
}

int main()
{
	fin = fopen( FIN, "r" );
	fout = fopen( FOUT, "w" );
	fscanf( fin, "%d%d", &N, &M );
	
	for( int i = 1; i <= N; i++ )
		V[i] = NULL;
	
	while( M )
	{
		fscanf( fin, "%d%d", &X, &Y );
		NR[X]++;
		push( V[Y], X );
		M--;
	}
	SortTop();
	fclose(fin);
	fclose(fout);
	return 0;
	
}