Cod sursa(job #149649)

Utilizator mithyPopovici Adrian mithy Data 5 martie 2008 22:24:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#include <vector>
#define NMax 50001

int n, m;
std::vector<int> a[NMax];
int pord[NMax], uz[NMax], lg;

void citire();
void rez();
void dfs(int x);

int main()
{
	citire();
	rez();
	return 0;
}
void dfs( int x )
{
	int i, lgx;

	uz[x] = 1;

	lgx = a[x].size();
	for (i=0; i<lgx; i++)
		if ( !uz[a[x][i]] )
			dfs(a[x][i]);

	pord[++lg] = x;
}
void rez()
{
	int i;

	for (i=1; i<=n; i++)
		if ( !uz[i] )
			dfs(i);

	for (i=n; i>0; i--)
		printf( "%d ", pord[i] );
}
void citire()
{
	int i, x, y;

	freopen( "sortaret.in", "rt", stdin );
	freopen( "sortaret.out", "wt", stdout );

	scanf( "%d %d", &n, &m );

	for (i=0; i<m; i++)
	{
		scanf( "%d %d", &x, &y );
		a[x].push_back(y);
	}
	
}