Cod sursa(job #1636601)

Utilizator bragaRObragaRO bragaRO Data 7 martie 2016 11:04:43
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb

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

using namespace std;

int m, n;

vector <vector <int> > graph;
stack <int> final_visited;
vector <bool> visited;
ifstream f("sortare.in");
ofstream h("sortare.out");
int nr_conexe = 0;

void dfs(int vertex)
{
	if (vertex<0 || vertex>n - 1) return;

	stack <int> s;
	int element, i;
	bool found;

	s.push(vertex);
	visited[vertex] = true;
	while (!s.empty())
	{
		element = s.top();
		found = false;
		for (i = 0; i < graph[element].size() && !found; i++)
			if (!visited[graph[element][i]]) found = true;

		if (found)
		{
			int k = i - 1;
			s.push(graph[element][k]);
			visited[graph[element][k]] = true;
		}
		else
        {
            final_visited.push(s.top());
            s.pop();
        }


	}

}


int main()
{
	int x, y, i;
	f >> n >> m;
	graph.resize(n);
	visited.resize(n, false);

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


	for (i = 0; i<visited.size(); i++)
		if (!visited[i]) { dfs(i);}

    for(i=0;i<visited.size();i++)
        {
        h << final_visited.top()+1 << " ";
        final_visited.pop();
        }

	f.close();
	h.close();
	return 0;
}