Cod sursa(job #705948)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 5 martie 2012 11:18:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector <long> A[50001], sol;
queue <long> coada;
long G[50001], x, y, N, M, i, j, elc;
bool viz[50001];

void sortaret(long i) {
	long j = 0;
	viz[i] = true;
	
	for (j = 0; j < G[i]; ++j) {
		if ( !viz[A[i][j]] ) {
			sortaret(A[i][j]);
		}
	}
	
	sol.push_back(i);
}

int main() {
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
		scanf("%ld %ld", &N, &M);
		
		for (i = 1; i <= M; ++i) {
			scanf("%ld %ld", &x, &y);
			A[x].push_back(y);
		}
		
		for (i = 1; i <= N; ++i) {
			G[i] = A[i].size();
		}
		
		for (i = 1; i <= N; ++i) {
			if ( !viz[i] ) {
				sortaret(i);
			}
		}
	
		for (vector<long>::reverse_iterator it = sol.rbegin(); it != sol.rend(); ++it)
			printf("%ld ", *it);
		
		printf("\n");
	
	return 0;
}