Cod sursa(job #651892)

Utilizator andreioneaAndrei Onea andreionea Data 22 decembrie 2011 02:26:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.52 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>

using namespace std;

class Node;
class Graf;

ostream &operator <<(ostream &out, vector<Node*> &st);

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), parent(parent), started_marking(false) {}
		Node *getNextNeighbor();
		int getNumber()const{return number;}
		
};

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

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(int n)
{
	visited.reserve(n);
	fill(visited.begin(), visited.begin() + n, false);
	for (int i = 0; i<n; ++i) {
		nodes.push_back(new Node(i, this));
	}
}

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


void Graf::addEdge(int x, int y)
{
	nodes[x]->addNeighbor(nodes[y]);
}

void Graf::computeTopology()
{
	if (!topology.empty()){
		return;
	}
	for (vector<Node*>::iterator it = nodes.begin(); it != nodes.end(); ++it)
		if (!visited[(*it)->number]) {
			dfs(*it);
		}
}

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


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, vector<Node*> &st)
{
	while (!st.empty()) {
		out << st.back()->getNumber() + 1 << " ";
		st.pop_back();
	}
	return out;
}

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