Cod sursa(job #1934311)

Utilizator dr55Dan Rusu dr55 Data 21 martie 2017 13:01:49
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>

const int kNAMX = 50005;
int numberOfNodes, totalEdges;
bool visited[100005];
using namespace std;
std::vector<int> G[kNMAX];
std::stack<int> S;



void read()
{
	std::ifstream fin("sortaret.in");
	fin >> numberOfNodes >> totalEdges;
	int x, y;
	for ( int i = 1; i <= totalEdges; i++)
	{
		fin >> x >> y;
		G[x].push_back(y);
	}
	fin.close();
}

void print()
{
	std::ofstream fout("sortaret.out");
	while ( !S.empty() )
	{
		fout << S.top() << ' ';
		S.pop();
	}
	fout << '\n';
	fout.close();
}

void dfs(int node)
{
	visited[node] = true;
	for (auto &it: G[node])
	{
		if (!visited[it])
		{
			dfs(it);
		}
	}
	S.push(node);
}

int main()
{
	read();
	for (int i = 1; i <= numberOfNodes; i++)
	{
		if (!visited[i])
		{
			dfs(i);
		}
	}
	print();
	return 0;
}