Cod sursa(job #1182812)

Utilizator abel1090Abel Putovits abel1090 Data 7 mai 2014 19:40:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
/// TOPOLOGICAL SORT
#include <fstream>
#include <vector>
#include <list>
using namespace std;

class Graph {
private:
	vector<list<unsigned> > adjList; /// !!! pop the edge (adjList[from].pop_front()) if ready
	vector<unsigned> numEdgesInto;
	unsigned numNodes, numEdges;
public:
	Graph(ifstream&);
	list<unsigned> getTopSort();
};

Graph::Graph(ifstream& inStr) {
	inStr >> numNodes >> numEdges;
	adjList.resize(numNodes);
	numEdgesInto.resize(numNodes, 0);

	unsigned from, to;
	for(unsigned i=0; i<numEdges; i++) {
		inStr >> from >> to;
		adjList[--from].push_back(--to);
		numEdgesInto[to]++;
	}
}

list<unsigned> Graph::getTopSort() {
	list<unsigned> nodesInOrder;
	list<unsigned> nodes;

	for(unsigned i=0; i<numNodes; i++)
		if(numEdgesInto[i] == 0)
			nodes.push_back(i);

	unsigned current;
	list<unsigned>::iterator it;
	while(!nodes.empty()) {
		current = nodes.front();
		nodes.pop_front();
		nodesInOrder.push_back(current);

		for(it = adjList[current].begin(); it != adjList[current].end(); it++) {
			numEdgesInto[*it]--;
			if(numEdgesInto[*it] == 0)
				nodes.push_back(*it);
		}
	}

	return nodesInOrder;
}

void printList(ofstream& outStr, list<unsigned>& l) {
	list<unsigned>::iterator it;
	for(it=l.begin(); it!=l.end(); it++)
		outStr << *it+1 << ' ';
	outStr << '\n';
}

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

	Graph graph(fin);
	list<unsigned> l = graph.getTopSort();
	printList(fout, l);
}