Cod sursa(job #1315714)

Utilizator Marius_mFMI-M2 Marius Melemciuc Marius_m Data 13 ianuarie 2015 00:43:19
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
/*
 * =====================================================================================
 *
 *       Filename:  topological_sort_directed.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  01/12/2015 23:53:36
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */

#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>

using namespace std;

vector<vector<int> > graph;
vector<bool> visited;

vector<int> topologicalSort(int vertex)
{
	stack<int> s;
	vector<int> result;

	s.push(vertex);
	visited[vertex] = true;

	while (!s.empty())
	{
		int element = s.top();
		bool found = false;
		int i;

		for (i = 0; i < graph[element].size() && (!found); i++)
			if (!visited[graph[element][i]])
				found = true;
		
		if (found)
		{
			i--;
			s.push(graph[element][i]);
			visited[graph[element][i]] = true;
		}
		else 
		{
			s.pop();
			result.push_back(element); // put the nodes while I pop them out of the stack
		}
	} /* while */

	return result;
}

int main(int argc, char** argv)
{
	int n, m;

	ifstream input("sortaret.in");
	ofstream output("sortaret.out");
	
	input >> n >> m;

	for (int i = 0; i < n; i++)
	{
		vector<int> row;
		graph.push_back(row);
		visited.push_back(false);
	}

	for (int i = 0; i < m; i++)
	{
		int x, y;
		
		input >> x >> y;
		graph[x].push_back(y);
	}

	vector<int> planning = topologicalSort(1);

	for (int i = 0; i < planning.size(); i++)
		output << planning[i] << " ";

	return 0;
}