Cod sursa(job #1315728)

Utilizator Marius_mFMI-M2 Marius Melemciuc Marius_m Data 13 ianuarie 2015 00:55:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
/*
 * =====================================================================================
 *
 *       Filename:  topological_sort_directed.cpp
 *
 *    Description: Planning tasks, for example task 4 depends on 1, 2, then we
				   consider edges (4, 1), (4, 2). 
 *
 *        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<int> planning;

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

void 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();
			planning.push_back(element); // put the nodes while I pop them out of the stack
		}
	} /* while */
}

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);
	}

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

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

	return 0;
}