Cod sursa(job #791435)

Utilizator feelshiftFeelshift feelshift Data 24 septembrie 2012 04:12:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
// Sorin Davidoi ([email protected]) - 2012-09-24 03:50
// http://infoarena.ro/problema/sortaret
#include <fstream>
#include <vector>
using namespace std;

const int MAXSIZE = 50000 + 1;

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

int nodesCount, edges;
bool visit[MAXSIZE];
int nodes[MAXSIZE];
vector<int> graph[MAXSIZE];

void depthFirst(int node) {
	visit[node] = true;
	vector<int>::iterator it = graph[node].begin();
	for(; it != graph[node].end(); ++it)
		if(!visit[*it])
			depthFirst(*it);

	nodes[++nodes[0]] = node;
}

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

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

	for (int i = 1; i <= nodesCount; ++i)
		if(!visit[i])
			depthFirst(i);

	for (int i = nodes[0]; i >= 1; --i)
		out << nodes[i] << ' ';
	out << '\n';

	in.close();
	out.close();

	return (0);
}