Cod sursa(job #1131449)

Utilizator axnsanCristi Vijdea axnsan Data 28 februarie 2014 20:13:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#ifdef __INFOARENA_PROJ
#include "infoarena.h"
#endif

#include <fstream>
#include <vector>

#ifdef __INFOARENA_PROJ
namespace sortaret {
#endif

const unsigned int maxN = 50000;
bool viz[maxN + 1];
std::vector<unsigned> G[maxN + 1];
unsigned reverseSortedOrder[maxN + 1], o;

void DFS(unsigned start)
{
	if (!viz[start])
	{
		viz[start] = true;
		for (std::vector<unsigned>::iterator it = G[start].begin(); it != G[start].end(); ++it)
			DFS(*it);
		reverseSortedOrder[++o] = start;
	}
}

int main()
{
	std::ifstream in("sortaret.in");
	std::ofstream out("sortaret.out");
	unsigned N, M, x, y;
	in >> N >> M;
	for (unsigned i = 0; i < M; ++i)
	{
		in >> x >> y;
		G[x].push_back(y);
	}
	for (unsigned nod = 1; nod <= N; ++nod)
		if (!viz[nod])
			DFS(nod);

	for (unsigned i = N; i > 0; --i)
		out << reverseSortedOrder[i] << ' ';
	out << '\n';

	return 0;
}


#ifdef __INFOARENA_PROJ
}
#endif