Cod sursa(job #1698737)

Utilizator vlad.dumitracheDumitrache Vlad vlad.dumitrache Data 5 mai 2016 10:46:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int n, m;

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

void dfs_sortaret(int vertex)
{
	if (vertex < 0 || vertex > n - 1) 
		return;
	
	stack<int> s;
	int element, i, top;
	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)
		{
			i--;
			s.push(graph[element][i]);
			visited[graph[element][i]] = true;
		}
		else
		{
			top = s.top();
			topologicalsort.push(top);
			s.pop();
		}
	}
}

int main()
{
	f >> n >> m;
	int i;
	graph.resize(n);
	visited.resize(n, false);
	int x, y;
	for (i = 0; i<m; i++)
	{
		f >> x >> y;
		x--;
		y--;
		graph[x].push_back(y);
	}

	for (i = 0; i<n; i++)
		if (!visited[i])
			dfs_sortaret(i);

	while (!topologicalsort.empty())
	{
		g << topologicalsort.top() +1 << " ";
		topologicalsort.pop();
	}

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