Cod sursa(job #2317216)

Utilizator DawlauAndrei Blahovici Dawlau Data 12 ianuarie 2019 22:47:35
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <list>
#include <vector>
#include <deque>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int VMAX = 50000;

list <int> adjList[1 + VMAX];
vector <int> inDeg;

int V, E;

void readData() {

	fin >> V >> E;

	inDeg.resize(1 + V);
	for (; E; --E) {

		int from, to;
		fin >> from >> to;

		adjList[from].push_back(to);
		++inDeg[to];
	}
}

void topoSort() {

	deque <int> Queue;

	for (int node = 1; node <= V; ++node)
		if (inDeg[node] == 0)
			Queue.push_back(node);

	while (!Queue.empty()) {

		int node = Queue.front();
		Queue.pop_front();

		fout << node << ' ';

		for (const int &nextNode : adjList[node]) {

			--inDeg[nextNode];
			if (inDeg[nextNode] == 0)
				Queue.push_back(nextNode);
		}
	}
}

int main() {

	readData();
	topoSort();
}