Cod sursa(job #1705032)

Utilizator laurentiu.piciuPiciu Laurentiu laurentiu.piciu Data 19 mai 2016 20:30:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>

int N, M;

using Graph = std::vector<std::vector<int> >;

Graph graph;
std::vector<bool> visited;
std::stack<int> topologicalStack;

void topsort_iterative_dfs(int start) {
	std::stack<int> stiva;
	visited[start] = true;
	stiva.push(start);

	while (!stiva.empty()) {
		int curr_node = stiva.top();
		bool ok = false;
		int first_unvisited;

		for (int neigh : graph[curr_node]) {
			if (!visited[neigh]) {
				ok = true;
				first_unvisited = neigh;
				break;
			}
		}

		if (ok) {
			visited[first_unvisited] = true;
			stiva.push(first_unvisited);
		} else {
			topologicalStack.push(curr_node);
			stiva.pop();
		}
	}
}

void topsort_recursive_dfs(int start) {
	visited[start] = true;
	for (int neigh : graph[start]) {
		if (!visited[neigh]) {
			topsort_recursive_dfs(neigh);
		}
	}
	topologicalStack.push(start);
}


int main() {
	std::ifstream f("sortaret.in");
	std::ofstream g("sortaret.out");

	f >> N >> M;

	graph.resize(N+1);
	visited.resize(N+1);

	for (int i = 0; i < M; ++i) {
		int from, to;
		f >> from >> to;
		graph[from].push_back(to);
	}

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			if (i % 2) 
				topsort_iterative_dfs(i);
			else
				topsort_recursive_dfs(i);
		}
	}

	while (!topologicalStack.empty()) {
		g << topologicalStack.top() << " ";
		topologicalStack.pop();
	}

	f.close(); g.close();

	return 0;
}