Cod sursa(job #2423785)

Utilizator nicu97oTuturuga Nicolae nicu97o Data 21 mai 2019 22:12:19
Problema Sortare topologica Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.34 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

void topologicalSort(stack<int>* sol, bool** graph, bool* visited, int currentNode, int size);

int areAllNodesVisited(bool* visited, int size);

void topologicalSort(stack<int>* sol, vector<vector<bool>> graph, vector<bool>* visited, int currentNode, int size);

int areAllNodesVisited(vector<bool> visited, int lastVisited, int size);

int main() {
	int n;
	int m;
	fin >> n;
	fin >> m;
	vector<bool> visited(n, false);
	vector<vector<bool>> graph(n, vector<bool>(n, false));
	int first, second;
	for (int i = 0; i < m; ++i) {
		fin >> first;
		fin >> second;
		graph.at(first - 1).at(second - 1) = true;
	}
	stack<int> sol;
	int currentNode = areAllNodesVisited(visited, 0, n);
	while (currentNode != -1) {
		topologicalSort(&sol, graph, &visited, currentNode, n);
		currentNode = areAllNodesVisited(visited, currentNode, n);

	}
	while (!sol.empty()) {
		fout << sol.top() << ' ';
		sol.pop();
	}
	return 0;
}

void topologicalSort(stack<int>* sol, vector<vector<bool>> graph, vector<bool>* visited, int currentNode, int size) {
	visited->at(currentNode) = true;
	for (int i = 0; i < size; ++i) {
		if (i == currentNode) {
			continue;
		}
		if (graph.at(currentNode).at(i) && !visited->at(i)) {
			topologicalSort(sol, graph, visited, i, size);
		}
	}
	sol->push(currentNode + 1);
}
int areAllNodesVisited(vector<bool> visited, int lastVisited, int size) {
	for (int i = lastVisited; i < size; ++i) {
		if (!visited.at(i)) {
			return i;
		}
	}
	return -1;
}

int areAllNodesVisited(bool* visited, int size) {
	for (int i = 0; i < size; ++i) {
		if (!visited[i]) {
			return i;
		}
	}
	return -1;
}

bool hasUnvisitedNeighbors(bool** graph, bool* visited, int currentNode, int size) {
	for (int i = 0; i < size; ++i) {
		if (graph[currentNode][i] && visited[i]) {
			return true;
		}
	}
	return false;
}

void topologicalSort(stack<int>* sol, bool** graph, bool* visited, int currentNode, int size) {
	visited[currentNode] = true;
	for (int i = 0; i < size; ++i) {
		if (i == currentNode) {
			continue;
		}
		if (graph[currentNode][i] && !visited[i]) {
			topologicalSort(sol, graph, visited, i, size);
		}
	}
	sol->push(currentNode + 1);
}