Cod sursa(job #1705897)

Utilizator m.scarlat95Scarlat Marius-George m.scarlat95 Data 21 mai 2016 02:18:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

#define MAX	100001

unsigned int n, m, in, out;
bool visited[MAX];
std::vector< std::vector <int> > edges;
std::vector<int> answer;


void dfs ( int root )
{
	visited[root] = true;
	for( unsigned int i = 0; i < edges[root].size(); ++i )
	{
		if( !visited[edges[root][i]] )
		{
			dfs(edges[root][i]);
		}
	}
	answer.push_back(root);
}

int main( void )
{
	freopen( "sortaret.in", "r", stdin );
	freopen( "sortaret.out", "w", stdout );

	std::cin >> n >> m; 
	edges.resize(n+1);
	for( unsigned int i = 0; i < m; ++i )
	{
		std::cin >> in >> out;
		edges[in].push_back(out); 
	}

	for( int i = 1; i <= n; ++i )
	{
		if( !visited[i] )
		{
			dfs(i);
		}
	}

	for(int i = n - 1 ; i >= 0; --i)
	{
		std::cout << answer[i] << ' ';
	}
	std::cout << "\n";

	fclose( stdin );
	fclose( stdout );
	return 0;
}