Cod sursa(job #499151)

Utilizator feelshiftFeelshift feelshift Data 8 noiembrie 2010 21:32:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
// http://infoarena.ro/problema/sortaret
#include <fstream>
#include <vector>
#include <list>
using namespace std;

int nodes,edges;
vector< list<int> > graph;
vector<bool> visit;
list<int> order;

void read();
void depthFirst(int toVisit);	// include sortarea topologica
void write();

int main() {
	read();

	for(int i=1;i<=nodes;i++)
		if(!visit.at(i))
			depthFirst(i);

	write();

	return (0);
}

void read() {
	ifstream in("sortaret.in");
	int from,to;

	in >> nodes >> edges;
	graph.resize(nodes+1);
	visit.resize(nodes+1);

	for(int i=1;i<=edges;i++) {
		in >> from >> to;

		graph.at(from).push_back(to);
	}

	in.close();
}

void depthFirst(int toVisit) {
	visit.at(toVisit) = true;

	for(list<int>::iterator it=graph.at(toVisit).begin();it!=graph.at(toVisit).end();it++)
		if(!visit.at(*it))
			depthFirst(*it);

	order.push_front(toVisit);	// sortarea topologica
}

void write() {
	ofstream out("sortaret.out");

	for(list<int>::iterator it=order.begin();it!=order.end();it++)
		out << *it << " ";

	/*for(int i=1;i<=nodes;i++)
		if(!visit.at(i))
			out << i << " ";*/

	//out << endl;

	out.close();
}