Cod sursa(job #1484809)

Utilizator DacianBocea Dacian Dacian Data 11 septembrie 2015 22:17:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

std::vector<int> g[50000];
int d[50000];

int main(){
	std::ifstream f("sortaret.in");
	std::ofstream c("sortaret.out");
	std::memset(d, 0, sizeof(d));
	int n,m,a,b;
	f >> n >> m;
	for (int i = 0; i < m; ++i) { f >> a >> b; g[a].push_back(b); ++d[b]; }
	std::queue<int> Q;
	for (int i = 1; i <= n; ++i) if (!d[i]) Q.push(i);
	int r;
	while (!Q.empty()){
		r = Q.front();
		Q.pop();
		for (auto& i : g[r]){
			--d[i];
			if (!d[i]) Q.push(i);
		}
		c << r << " ";
	}
}