Cod sursa(job #2316646)

Utilizator DawlauAndrei Blahovici Dawlau Data 12 ianuarie 2019 03:57:41
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <list>
#include <vector>
#include <deque>
#include <bitset>

using namespace std;

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

const int VMAX = 50000;

list <int> adjList[1 + VMAX];
vector <int> outDeg;
bitset <1 + VMAX> seen;

int V, E;

void readData() {

	fin >> V >> E;

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

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

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

void topoSort() {

	deque <int> Queue;
	for (int node = 1; node <= V; ++node)
		if (outDeg[node] == 0) {

			seen[node] = true;
			Queue.push_back(node);
		}

	while (!Queue.empty()) {

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

		fout << node << ' ';

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

				Queue.push_back(nextNode);
				seen[nextNode] = true;
			}
	}
}

int main() {

	readData();
	topoSort();
}