Cod sursa(job #1484812)

Utilizator tain1234andrei laur tain1234 Data 11 septembrie 2015 22:38:57
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
int main(){
	ifstream f("sortaret.in");
	ofstream of("sortaret.out");
	vector<int> Nout[50001];
	int deg[50001];
	memset(deg, 0, sizeof(deg));
	queue<int> q;
	int N,M,x, y;
	f >> N >> M;
	for (int i = 0; i < M; ++i){
		f >> x >> y;
		Nout[x].push_back(y);
		++deg[y];
	}
	for (int i = 1; i <= N;++i)
		if (!deg[i])q.push(i);
	while (!q.empty()){
		x = q.front();
		q.pop();
		for (auto& i : Nout[x]){
			--deg[i];
			if (!deg[i])q.push(i);
		}
		of << x << " ";
		}
	return 0;
}