Cod sursa(job #383083)

Utilizator raduzerRadu Zernoveanu raduzer Data 15 ianuarie 2010 16:36:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <vector>
using namespace std;

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

const int MAX_N = 50010;

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

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 r1, r2;
		scanf("%d %d", &r1, &r2);

		v[r1].pb(r2);
		++g[r2];
	}

	for (i = 1; i <= n; ++i)
		if (!g[i])
			sol[++z] = i;

	for (i = 1; i <= z; ++i)
		forit(it, v[sol[i]])
		{
			--g[*it];

			if (!g[*it])
				sol[++z] = *it;
		}

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