Cod sursa(job #606483)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 4 august 2011 16:10:16
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 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> sorted;

void TopSort(const Graph& graph, const int node)
{
	visited[node] = 1;
	for (int i=0; i<graph[node].size(); ++i)
	{
		if (!visited[graph[node][i]])
		{
			TopSort(graph, graph[node][i]);
		}
	}
	
	sorted.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);
	}
	
	for (int i=0; i<n; ++i)
	{
		if (!visited[i])
		{
			TopSort(graph, i);
		}
	}

	for (int i=0; i<n; ++i)
	{
		fout << sorted[i]+1 << " ";
	}
	fout << endl;
	
	return 0;
}