Cod sursa(job #1449556)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 9 iunie 2015 23:30:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stack>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
using bag = stack<T, vector<T>>;

vector<int> toposort(const vector<vector<int>>& graf){
	vector<int> ret, in_deg(graf.size(), 0);
	for(const auto& x : graf){
		for(const auto y : x){
			++in_deg[y]; } }
	bag<int> de_viz;
	for(int i = 0; i < graf.size(); ++i){
		if(in_deg[i] == 0){
			de_viz.push(i); } }
	for(int cur ; ret.size() < graf.size(); ){
		cur = de_viz.top();
		de_viz.pop();
		ret.push_back(cur);
		for(const auto next : graf[cur]){
			--in_deg[next];
			if(!in_deg[next]){
				de_viz.push(next); } } }
	return ret; }

vector<vector<int>> citeste_graf(ifstream& f){
	vector<vector<int>> graf;
	int n, m;
	f >> n >> m;
	graf.resize(n);
	for(int i = 0, a, b; i < m; ++i){
		f >> a >> b;
		graf[a-1].push_back(b-1); }
	return graf; }

int main(){
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");
	const auto& sortare = toposort(citeste_graf(f));
	for(const auto x : sortare){
		g << (x+1) << ' ' ; }
	return 0; }