Cod sursa(job #1705795)

Utilizator KaliNarcisa Vasile Kali Data 20 mai 2016 23:33:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility> 
#include <stack>

typedef unsigned int uint;
using namespace std; 

vector <vector<int> > arce;
ofstream out("sortaret.out");

void topsort(vector<int>& grad_in, int n) {
	stack<int> s;
	for (int i = 1; i <=n; ++i)
		if (grad_in[i] == 0)
			s.push(i);
	vector<int> result;
	while(!s.empty()) {
		int nod = s.top();
		s.pop();
		result.push_back(nod);
		for (uint i = 0; i < arce[nod].size(); ++i) {
			--grad_in[arce[nod][i]];
			if (grad_in[arce[nod][i]] == 0)
				s.push(arce[nod][i]);
		}
	}
	for (uint i = 0; i < result.size(); ++i)
		out << result[i] << " ";
	out << '\n';
}
int main() {

	ifstream in("sortaret.in");
	
	int n, m;
	in >> n >> m; 
	arce.reserve(n+1);
	int x, y;
	vector<int> grad_in(n+1, 0);
	for (int i = 0; i < m; ++i) {
		in >> x >> y;
		arce[x].push_back(y);
		++grad_in[y];
	}
	topsort(grad_in, n);
}