Cod sursa(job #2307891)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 25 decembrie 2018 20:28:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
#include <stack>

#define input "sortaret.in"
#define output "sortaret.out"
#define NMAX 50005

using namespace std;

ifstream in(input);
ofstream out(output);

vector < int > vecini[NMAX];
stack < int > sol;

int noduri, arce, uz[NMAX];

void Read_Data()
{
	in >> noduri >> arce;
	for (int i = 1; i <= arce; i++)
	{
		int x, y;
		in >> x >> y;
		vecini[x].push_back(y);
	}
}

void DFS(int nod)
{
	uz[nod] = 1;
	for (unsigned i = 0; i < vecini[nod].size(); i++)
	{
		int new_nod = vecini[nod][i];
		if (!uz[new_nod])
		DFS(new_nod);
	}
	sol.push(nod);
}

void Solve()
{
	for (int i = 1; i <= noduri; i++)
	if (!uz[i]) DFS(i);
}

void Print_Sol()
{
	while (!sol.empty())
	{
		out << sol.top() << " ";
		sol.pop();
	}
}

int main()
{
	Read_Data();
	Solve();
	Print_Sol();
	return 0;
}