Cod sursa(job #606476)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 4 august 2011 15:36:35
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <string.h>

using namespace std;

typedef vector<vector<int> > Graph;

#define MAXN 50000

int visited[MAXN];
vector<int> sort;

/*int TopSort(const Graph& graph, stack<int>& sort)
{
	int *visited;
	stack<int> st;
	visited = new int[graph.size()];
	
	memset(visited, 0, sizeof(int)*graph.size());

	st.push(0);
	visited[0] = 1;
	
	while (!st.empty())
	{
		const int node = st.top();
		st.pop();

		sort.push(node);
		
		for (int i=0; i<graph[node].size(); ++i)
		{	
			visited[graph[node][i]] = 1;
			st.push(graph[node][i]);
		}
	}
	
	delete visited;
	
	return 1;
}*/

void TopSort(const Graph& graph, const int node)
{
	for (int i=0; i<graph[node].size(); ++i)
	{
		if (!visited[graph[node][i]])
			TopSort(graph, graph[node][i]);
	}
	
	sort.push_back(node);
}

int main()
{
	int n, m;
	fstream fin("sortaret.in", fstream::in);
	fstream fout("sortaret.out", fstream::out);
	Graph graph;
	
	fin >> n >> m;
	
	graph.resize(n);
	
	for (int i=0; i<m; ++i)
	{
		int x, y;
		fin >> x >> y;
		
		graph[x-1].push_back(y-1);
	}
	
	TopSort(graph, 0);
	
	for (int i=0; i<n; ++i)
	{
		fout << sort[i]+1 << " ";
	}
	fout << endl;
	
	return 0;
}