Cod sursa(job #425301)

Utilizator raduzerRadu Zernoveanu raduzer Data 25 martie 2010 17:12:08
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define forit(it, v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
#define pb push_back

const int MAX_N = 50010;

int n, m, z;
int sol[MAX_N], f[MAX_N];
vector <int> v[MAX_N];

void df(int nod)
{
	if (f[nod])
		return;
	f[nod] = 1;

	forit(it, v[nod])
		df(*it);

	sol[++z] = nod;
}

int main()
{
	int i;
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

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

	for (i = 1; i <= m; ++i)
	{
		int x, y;

		scanf("%d %d", &x, &y);

		v[x].pb(y);
		f[y] = 1;
	}

	int rad = 0;

	for (i = 1; i <= n; ++i)
		if (!f[i])
			rad = i;

	memset(f, 0, sizeof(f));
	df(rad);

	for (i = n; i; --i)
		printf("%d ", sol[i]);
}