Cod sursa(job #676874)

Utilizator marius135Dumitran Adrian Marius marius135 Data 9 februarie 2012 17:56:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
// Sotare topologica - Infoarena Arhiva Educationala
// Dumitran Marius Feb 2012 
// O(n+m)

#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

#define maxn 50001

vector <int> vec[maxn];
vector <int> solutie;
int nr[ maxn ];

int main() {
	
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	
	int n, m;
	scanf("%d %d", &n, &m);
	
	for( int i = 1; i <= m; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		nr[b]++;
		vec[a].push_back(b);
	}
	for( int i = 1; i <= n; ++i) {
		if(nr[i] == 0) 
			solutie.push_back(i);
	}
	for( int i = 0; i < solutie.size(); ++i) {
		int new_nod = solutie[i];
		printf("%d ", new_nod);
		for( int j = 0; j < vec[ new_nod ].size(); ++j) {
			nr[ vec[ new_nod ][j]]--;
			if( nr[ vec[ new_nod][j]] == 0) {
				solutie.push_back(vec[new_nod][j]);
			}
		}
	}
	printf("\n");
	
	
	
	return 0;
}