Cod sursa(job #180109)

Utilizator sims_glAlexandru Simion sims_gl Data 16 aprilie 2008 17:36:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define nm 50010

int n, m, g[nm], l = 1, r = 1, q[nm];
vector<int> mat[nm];

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

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

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

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

		mat[x].push_back(y);
		g[y]++;
	}

	for (int i = 1; i <= n; ++i)
		if (!g[i])
			q[r++] = i;

	while (l < r) {
		int crt = q[l];

		printf("%d ", crt);

		for (int i = mat[crt].size() - 1; i >= 0; --i) {
			g[mat[crt][i]]--;
			if (!g[mat[crt][i]])
				q[r++] = mat[crt][i];
		}

		++l;
	}

	printf("\n");

	return 0;
}