Cod sursa(job #953937)

Utilizator gabrieligabrieli gabrieli Data 27 mai 2013 20:33:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

void dfs (int vertex,
		const vector <vector <int>> &G,
		vector <bool> &seen,
		stack <int> &tsort)
{
	seen[vertex] = true;

	for (int i = 0; i < G[vertex].size(); ++i)
		if ( !seen[G[vertex][i]] )
			dfs (G[vertex][i], G, seen, tsort);

	tsort.push (vertex);
}

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

	int n, m;
	fin >> n >> m;

	vector <vector <int>> G (n+1, vector <int> ());

	for (; m; --m)
	{
		int x, y;
		fin >> x >> y;

		G[x].push_back (y);
	}

	stack <int> tsort;
	vector <bool> seen = vector <bool> (n+1, false);

	for (int i = 1; i <= n; ++i)
		if (!seen[i])
		{
			dfs (i, G, seen, tsort);
		}


	while (!tsort.empty())
	{
		fout << tsort.top() << ' ';
		tsort.pop();
	}
	fout << endl;

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