Cod sursa(job #1337484)

Utilizator BionicMushroomFMI - Dumitrescu Tiberiu Alexandru BionicMushroom Data 9 februarie 2015 02:57:35
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

int main()
{
	vector<short> *successors, sorted;
	short vertex_number, from, to;
	int *predecessors_number, edge_number;
	queue<short> q;
	ifstream in_file("sortaret.in");
	in_file >> vertex_number >> edge_number;
	successors = new vector<short>[vertex_number];
	predecessors_number = new int[vertex_number];
	for (short i = 0; i < vertex_number; ++i)
		predecessors_number[i] = 0;
	while (edge_number--)
	{
		in_file >> from >> to;
		successors[from - 1].push_back(to - 1);
		++predecessors_number[to - 1];
	}
	in_file.close();
	for (short i = 0; i < vertex_number; ++i)
		if (!predecessors_number[i])
			q.push(i);
	do
	{
		sorted.push_back(q.front());
		for (auto successor : successors[q.front()])
			if (!(--predecessors_number[successor]))
				q.push(successor);
		q.pop();
	} while (!q.empty());
	ofstream out_file("sortaret.out");
	for (auto node : sorted)
		out_file << node + 1 << ' ';
	delete[] successors;
	delete[] predecessors_number;
}