Cod sursa(job #2456084)

Utilizator mvcl3Marian Iacob mvcl3 Data 13 septembrie 2019 16:42:44
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>
#include<string>
#include<vector>
#include<queue>
#include<queue>

const std::string inFileName = "sortaret.in";
const std::string outFileName = "sortaret.out";
const int MAX_EDGES = 50001;

std::vector<int> sort(std::vector<int>& cntInputs, std::vector<std::vector<int>>& vertices) {
	std::queue<int> q;
	std::vector<int> sorted(cntInputs.size() - 1);
	int inserted = 0;

	for (size_t i = 1; i < cntInputs.size(); ++i) {
		if (!cntInputs[i]) {
			q.push(i);
			sorted[inserted++] = i;
		}
	}
	
	while (!q.empty()) {
		int node = q.front();
		q.pop();

		for (auto& n : vertices[node]) {
			if (!cntInputs[n]) {
				continue;
			}

			cntInputs[n] --;
			if (!cntInputs[n]) {
				q.push(n);
				sorted[inserted++] = n;
			}
		}
	}
	//if inserted < sorted.size() means that there we have a cycle
	return std::move(sorted);
}

int main() {
	int n, m;
	std::ifstream in(inFileName);
	std::ofstream out(outFileName);

	in >> n >> m;
	std::vector<int> cntInputs(n + 1);
	std::vector<std::vector<int>> vertices(n + 1);

	for (size_t x, y, i = 1; i <= m; ++i) {
		in >> x >> y;
		cntInputs[y] ++;
		vertices[x].push_back(y);
	}

	std::vector<int> sorted = sort(cntInputs, vertices);
	for (auto& node : sorted) {
		out << node << ' ';
	}

	return 0;
}