Cod sursa(job #651888)

Utilizator andreioneaAndrei Onea andreionea Data 22 decembrie 2011 02:07:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.37 kb
//Sortare topologica, facuta all OOP and stuff
//Ar trebui sa aiba un punctaj foarte scazut, dar e for teh lulz, anyways

#include <fstream>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;
class Node;
class Graf;

class Node
{
	friend class Graf;
	private:
		int number;
		vector<Node*> neighbors;
		vector<Node*>::iterator iterator;
		Graf *parent;
		bool started_marking;
		void addNeighbor(Node *node) {neighbors.push_back(node);}
	public:
		Node (int number, Graf* parent):number(number), started_marking(false), parent(parent) {}
		Node *getNextNeighbor();
		int getNumber()const{return number;}
		
};

class Graf{
	friend class Node;
	private:
		vector<bool> visited;			
		vector<Node*> nodes;
		void dfs(Node *node);
		stack<Node*> topology;
	public:
		Graf(int n); 
		~Graf();
		void addEdge(int x, int y);
		stack<Node*> computeTopology();
	friend istream &operator >>(istream &in, Graf *&gr); 
};

void Graf::dfs(Node *node)
{
	Node *vec; 
	visited[node->number] = true;
	while(vec = node->getNextNeighbor()) 
		dfs(vec);
	topology.push(node);
}

stack<Node*> Graf::computeTopology()
{
	if (!topology.empty()){
		return topology;
	}
	for (int i = 0; i<nodes.size(); ++i)
		if (!visited[i]) {
			dfs(nodes[i]);
		}
	return topology;
}
void Graf::addEdge(int x, int y)
{
	nodes[x]->addNeighbor(nodes[y]);
}

Graf::Graf(int n)
{
	
	for (int i = 0; i<n; ++i) {
		nodes.push_back(new Node(i, this));
		visited.push_back(false);
	}
}

istream &operator >>(istream &in, Graf *&gr)
{
	int n, m;
	in >> n >> m;
	gr = new Graf(n);
	int x, y;
	for (int i = 0; i<m; ++i) {
		in >> x >> y;
		gr->addEdge(x-1,y-1);
	}
	return in;
}

ostream &operator <<(ostream &out, stack<Node*> &st)
{
	while (!st.empty()) {
		out << st.top()->getNumber() + 1 << " ";
		st.pop();
	}
	return out;
}

Node *Node::getNextNeighbor() 
{
	if (!started_marking) {
		iterator = neighbors.begin();
		started_marking = true;
	}
		
	while (true) {	
		if (iterator == neighbors.end()) {
			started_marking = false;
			return 0;
		}
		
		Node *ret = *iterator;
		++iterator;
		if (!parent->visited[ret->number])
			return ret;
	}
	return 0;
}


Graf::~Graf()
{
	for (int i = 0; i<nodes.size(); ++i)
		delete nodes[i];
}

int main()
{
	ifstream fin("sortaret.in");
	ofstream fout("sortaret.out");
	Graf *g;
	fin >> g;
	fin.close();
	stack<Node*> st = g->computeTopology();
	fout << st << endl;
	fout.close();
	delete g;
	return 0;
}