Cod sursa(job #1181554)

Utilizator ELHoriaHoria Cretescu ELHoria Data 3 mai 2014 03:16:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.35 kb
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdexcept>
#include <stack>

using namespace std;

class Graph
{
protected:

	int vertexNumber;
	int edgeNumber;
	vector< vector<int> > data;

	virtual void readData(istream& in);

	virtual void writeData(ostream& out);

public:

	Graph(int vertexNumber_);

	Graph(int vertexNumber_, int edgeNumber, const vector< pair<int, int> >& edges);

	virtual ~Graph();

	int getVertexNumber() const;

	virtual void addEdge(const int&x, const int& y);

	friend istream& operator >> (istream& in, Graph& graph);

	friend ostream& operator << (ostream& out, Graph& graph);

};

Graph::Graph(int vertexNumber_ = 0) {
	vertexNumber = vertexNumber_;
	data.resize(vertexNumber);
}

Graph::Graph(int vertexNumber_, int edgeNumber_, const vector< pair<int, int> >& edges) {
	vertexNumber = vertexNumber_;
	edgeNumber = edgeNumber_;
	data.resize(vertexNumber);
	for (const auto& edge : edges) {
		addEdge(edge.first, edge.second);
	}
}

Graph::~Graph() {
	vertexNumber = 0;
}


void Graph::addEdge(const int& x, const int& y) {
	try {
		if (x < 0 || x >= vertexNumber || y < 0 || y >= vertexNumber) {
			out_of_range outException("Node index out of bounds!");
			throw outException;
		}
		data[x].push_back(y);
		data[y].push_back(x);
	}

	catch (out_of_range& exception) {
		cout << exception.what() << "\n";
	}
}

void Graph::readData(istream& in) {
	in >> vertexNumber >> edgeNumber;
	data.clear();
	data.resize(vertexNumber);
	int a, b;
	for (int i = 0; i < edgeNumber; i++) {
		in >> a >> b;
		a--, b--;
		addEdge(a, b);
	}
}

void Graph::writeData(ostream& out) {
	out << vertexNumber << " " << edgeNumber << "\n";
	for (int v = 0; v < vertexNumber; v++) {
		for (const int& w : data[v]) {
			if (v < w) {
				out << v << " " << w << "\n";
			}
		}
	}
}

istream& operator >> (istream& in, Graph& graph) {
	graph.readData(in);
	return in;
}

ostream& operator << (ostream& out, Graph& graph) {
	graph.writeData(out);
	return out;
}



class DirectedGraph : public Graph
{

	public:

		virtual	void addEdge(const int& x, const int& y);

		vector<int> getTopologicalSort();

};

vector<int> DirectedGraph::getTopologicalSort() {
	vector<int> sortedOrder;

	vector <bool> visited(vertexNumber, false);

	vector< vector<int>::iterator > nextNode(vertexNumber);

	stack<int> s;
	

	for (int i = 0; i < vertexNumber; i++) {
		if (!visited[i]) {
			int v = i;
			s.push(v);
			while (!s.empty()) {
				v = s.top();
				if (!visited[v]) {
					visited[v] = true;
					nextNode[v] = begin(data[v]);
				}
			
				bool allDone = true;

				while (allDone && nextNode[v] != end(data[v])) {
					auto w = *(nextNode[v]++);
					if (!visited[w]) {
						s.push(w);
						allDone = false;
					} 
				}

				if (allDone) {
					sortedOrder.push_back(v);
					s.pop();
				} 
			}
		}
	}

	reverse(begin(sortedOrder), end(sortedOrder));
	return sortedOrder;
}


void  DirectedGraph::addEdge(const int& x, const int& y) {
	data[x].push_back(y);
}

int main() {

	ifstream cin("sortaret.in");
	ofstream cout("sortaret.out");
	DirectedGraph G;
	cin >> G;
	vector<int> nodes = G.getTopologicalSort();
	for (auto& x : nodes) 
		cout << x + 1 << " ";
	return 0;
}