Cod sursa(job #160983)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 17 martie 2008 14:06:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <stdio.h>
#include <vector>

using namespace std;

vector <int> a[50001];

long i, j, n, m, x, y, pen[50001], b[50001];

void show() {
	for (long i = 1; i <= n; ++i) {
		printf("%ld ", pen[i]);
	}
}

int main() {
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%ld %ld\n", &n, &m);
	for (i = 1; i <= m; ++i){
		scanf("%ld %ld\n", &x, &y);
		a[x].push_back(y);
		++b[y];		
	}

	for (i = 1; i <= n; ++i) {
		if (b[i] == 0) {
			pen[++pen[0]] = i;
		}
	}
	
	for (i = 1; i <= n; ++i) {
		x = pen[i];
		for (j = 0; j < a[x].size(); ++j) {
			y = a[x][j];
			--b[y];			
			if (b[y] == 0) {
				pen[++pen[0]] = y;
			}
		}
	}
	show();
	return 0;
}