Cod sursa(job #2423736)

Utilizator nicu97oTuturuga Nicolae nicu97o Data 21 mai 2019 21:42:00
Problema Sortare topologica Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <stack> 
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);

int main() {
	int n;
	int m;
	fin >> n;
	fin >> m;
	bool* visited = (bool*)malloc(sizeof(bool) * n);
	for (int i = 0; i < n; ++i) {
		visited[i] = false;
	}
	bool** graph = (bool**)malloc(sizeof(bool*) * n);
	for (int i = 0; i < n; ++i) {
		graph[i] = (bool*)malloc(sizeof(bool) * n);
		for (int j = 0; j < n; ++j) {
			graph[i][j] = false;
		}
	}
	int first, second;
	for (int i = 0; i < m; ++i) {
		fin >> first;
		fin >> second;
		graph[first - 1][second - 1] = true;
	}
	stack<int> sol;
	int currentNode = areAllNodesVisited(visited, n);
	while (currentNode != -1) {
		topologicalSort(&sol, graph, visited, currentNode, n);
		currentNode = areAllNodesVisited(visited, n);
	}
	while (!sol.empty()) {
		fout << sol.top() << ' ';
		sol.pop();
	}
	for (int i = 0; i < n; ++i) {
		free(graph[i]);
	}
	free(graph);
	free(visited);
	return 0;
}

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