Cod sursa(job #505880)

Utilizator darrenRares Buhai darren Data 4 decembrie 2010 12:58:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>

using namespace std;

void Dfs(int x);

int N, M;
vector<int> V[50002];
bool S[50002];
vector<int> sol;

int main()
{
	ifstream fin("sortaret.in");
	ofstream fout("sortaret.out");

	fin >> N >> M;
	for (int i = 1, nod1, nod2; i <= M; ++i)
	{
		fin >> nod1 >> nod2;
		V[nod1].push_back(nod2);
	}

	for (int i = 1; i <= N; ++i)
		if (!S[i])
			Dfs(i);

	for (vector<int>::reverse_iterator it = sol.rbegin(); it != sol.rend(); ++it)
		fout << *it << ' ';

	fin.close();
	fout.close();
}

void Dfs(int x)
{
	S[x] = true;

	for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
		if (!S[*it])
			Dfs(*it);

	sol.push_back(x);
}