Cod sursa(job #494088)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 20 octombrie 2010 18:38:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
#include <vector>
#include <bitset>
#define maxN 50010
using namespace std;
bitset <maxN> viz;
vector <int> g[maxN];
int sol[maxN], cnt, i, n, m;
void df (int node)
{
	viz[node] = 1;
	for (vector <int> :: iterator it = g[node].begin (); it != g[node].end (); it += 1)
		if (!viz[*it])
			df (*it);
	sol[++cnt] = node;
}
int main ()
{
	freopen ("sortaret.in", "r", stdin);
	freopen ("sortaret.out", "w", stdout);
	
	int x, y;
	scanf ("%d %d\n", &n, &m);

	while (m--)
	{
		scanf ("%d %d\n", &x, &y);
		g[x].push_back (y);
	}
	for (i = 1; i <= n; i++)
		if (!viz[i])
			df (i);
	for (i = cnt; i >= 1; i--)
		printf ("%d ", sol[i]);
	return 0;
}