Cod sursa(job #443713)

Utilizator TabaraTabara Mihai Tabara Data 17 aprilie 2010 23:00:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <vector>

const int NMAX = 50005;
const char* in = "sortaret.in";
const char* out = "sortaret.out";

using namespace std;

vector <int> L[NMAX];
int N, M, grad[NMAX], Q[NMAX];

int main (void)
{
	freopen ( in, "r", stdin );
	freopen ( out, "w", stdout );

	scanf ("%d%d", &N, &M);

	int i, X, Y;
	vector <int>::iterator it;

	for ( ; M; --M)
	{
		scanf ( "%d%d", &X, &Y );
		L[X].push_back ( Y );
		grad[Y]++;
	}

	for (i = 1; i <= N; ++i)
		if (!grad[i]) Q[++Q[0]] = i;

	for (i = 1; i <= N; ++i)
	{
		for (it = L[Q[i]].begin(); it != L[Q[i]].end(); ++it )
			if ( !(--grad[*it]) ) Q[++Q[0]] = *it;
	}

	for ( i = 1;  i <= N; ++i)
		printf ( "%d ", Q[i] );

	return 0;
}