Cod sursa(job #247665)

Utilizator ilincaSorescu Ilinca ilinca Data 23 ianuarie 2009 18:03:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>
#include <vector>
#include <queue>

#define nmax 50005
#define mmax 100005

using namespace std;

int n, m;
int ns [nmax];
queue <int> q;
vector <int> g [nmax];

void scan ()
{
	int i, a, b;
	scanf ("%d%d", &n, &m);
	for (i=1; i <= m; ++i)
	{
		scanf ("%d%d", &a, &b);
		g [a].push_back (b);
		++ns [b];
	}
}

void init ()
{
	int i;
	for (i=1; i <= n; ++i)
		if (! ns [i])
			q.push (i);
}

void bfs ()
{
	int i;
	vector <int>::iterator it;
	while (! q.empty ())
	{
		i=q.front ();
		printf ("%d ", i);
		for (it=g [i].begin (); it != g [i].end (); ++it)
		{
			--ns [*it];
			if (! ns [*it])
				q.push (*it);
		}
		q.pop ();
	}
}

int main ()
{
	freopen ("sortaret.in", "r", stdin);
	freopen ("sortaret.out", "w", stdout);
	scan ();
	init ();
	bfs ();
	printf ("\n");
	return 0;
}