Cod sursa(job #662720)

Utilizator feelshiftFeelshift feelshift Data 16 ianuarie 2012 22:26:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
// http://infoarena.ro/problema/sortaret
#include <fstream>
#include <vector>
#include <list>
using namespace std;

const int MAXSIZE = 50001;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

int nodes,edges;
bool visited[MAXSIZE];
vector<int> graph[MAXSIZE];
list<int> solution;

void depthFirst(int node);

int main()
{
	in >> nodes >> edges;

	int from,to;
	for(int i=1;i<=edges;i++)
	{
		in >> from >> to;
		graph[from].push_back(to);
	}

	in.close();

	for(int i=1;i<=nodes;i++)
		if(!visited[i])
			depthFirst(i);

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

	out.close();

	return (0);
}

void depthFirst(int node)
{
	visited[node] = true;
	vector<int>::iterator neighbour;
	vector<int>::iterator end = graph[node].end();

	for(neighbour=graph[node].begin();neighbour!=end;++neighbour)
		if(!visited[*neighbour])
			depthFirst(*neighbour);

	solution.push_front(node);
}