Cod sursa(job #156480)

Utilizator plastikDan George Filimon plastik Data 12 martie 2008 16:20:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
// Sortare Topologica
// http://infoarena.ro/problema/sortaret

#include <cstdio>
#include <vector>
using namespace std;

#define NMAX 50005

int Deg[NMAX], Used[NMAX], n, m;
vector<int> Neighb[NMAX], Sol;

void depthFirst(int n) {
	int i, sz = Neighb[n].size();

	for (i = 0; i < sz; ++ i)
		if (Used[Neighb[n][i]] == false) {
			Used[Neighb[n][i]] = true;
			depthFirst(Neighb[n][i]);
		}

	Sol.push_back(n);
}

int main() {

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

	scanf("%d %d", &n, &m);
	int i, v1, v2;
	for (i = 0; i < m; ++ i) {
		scanf("%d %d", &v1, &v2);
		Neighb[v1 - 1].push_back(v2 - 1);
		-- Deg[v2 - 1];
	}

	for (i = 0; i < n; ++ i)
		if (Deg[i] == 0) {
			Used[i] = true;
			depthFirst(i);
		}

	for (i = Sol.size() - 1; i >= 0; -- i)
		printf("%d ", Sol[i] + 1);

	return 0;
}