Cod sursa(job #606473)

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

using namespace std;

typedef vector<vector<int> > Graph;

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

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

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

int main()
{
	int n, m;
	fstream fin("sortaret.in", fstream::in);
	fstream fout("sortaret.out", fstream::out);
	Graph graph;
	vector<int> sort;
	
	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);
	}
	
	if (TopSort(graph, n, sort))
	{
		for (int i=0; i<n; ++i)
			fout << sort[i]+1 << " ";
		fout << endl;
	}
	
	return 0;
}