Cod sursa(job #2430602)

Utilizator AxellApostolescu Alexandru Axell Data 15 iunie 2019 15:38:35
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.75 kb
#include <iostream>
#include <fstream>

#include <vector>
#include <algorithm>

struct Node {
	std::vector<int> neigh;
};

class ListGraph {
 private:
 	int size;
 	std::vector<Node> nodes;
 public:
 	explicit ListGraph(int size) {
 		this->size = size;
 		for (int i = 0 ; i < size ; ++i) {
 			Node tmp;
 			nodes.push_back(tmp);
 		}
 	}

 	~ListGraph() {

 	}

 	void addEdge(int src, int dst) {
 		if (src < 0 || src >= size || dst < 0 || dst >= size) {
 			std::cout << "Problem with nodes\n";
 			return;
 		}
 		if (hasEdge(src, dst)) {
 			return;
 		}
 		nodes[src].neigh.push_back(dst);
 	}

 	bool hasEdge(int src, int dst) {
 		if (src < 0 || src >= size || dst < 0 || dst >= size) {
 			std::cout << "Problem with nodes\n";
 			return false;
 		}
 		std::vector<int>::iterator it;
 		it = std::find(nodes[src].neigh.begin(), nodes[src].neigh.end(), dst);
 		if (it != nodes[src].neigh.end()) {
 			return true;
 		}
 		return false;
 	}

 	void removeEdge(int src, int dst) {
 		if (src < 0 || src >= size || dst < 0 || dst >= size) {
 			std::cout << "Problem with nodes\n";
 			return;
 		}

 		for (auto it = nodes[src].neigh.begin() ; it != nodes[src].neigh.end()
 																	; ++it) {
 			if (*it == dst) {
 				nodes[src].neigh.erase(it);
 				return;
 			}
 		}
 	}

 	std::vector<int> getNeighbors(int node) {
 		if (node < 0 || node >= size) {
 			std::cout << "Problem with the node\n";
 			return std::vector<int>();
 		}
 		return nodes[node].neigh;
 	}

 	int getSize() {
 		return size;
 	}

 	std::vector<int> sortareTopologica() {
 		std::vector<int> result;
 		std::vector<bool> visited(size, false);
 		for (int i = 0 ; i < size ; ++i) {
 			if (!visited[i]) {
 				std::vector<int> v;
 				v = DFS(i, visited);
 				for (auto elem : v) {
 					result.push_back(elem);
 				}
 			}
 		}
 		return result;
 	}

 	std::vector<int> DFS(int node, std::vector<bool>& visited) {
 		std::vector<int> result;
 		visited[node] = true;
 		result.push_back(node);
 		for (unsigned int i = 0 ; i < getNeighbors(node).size() ; ++i) {
 			if (!visited[getNeighbors(node)[i]]) {
 				std::vector<int> v = DFS(getNeighbors(node)[i], visited);
 				for (auto elem : v) {
 					result.push_back(elem);
 				}
 			}
 		}
 		return result;
 	}
};

using namespace std;

int main() {
	ifstream in;
	in.open("sortaret.in");
	ofstream out;
	out.open("sortaret.out");
	if (!in || !out) {
		std::cout << "Problem with opening files!\n";
		return -1;
	}

	//  Citire
	int numNodes, numEdges;
	in >> numNodes >> numEdges;
	ListGraph list(numNodes);
	for (int i = 0 ; i < numEdges ; ++i) {
		int a, b;
		in >> a >> b;
		list.addEdge(a - 1, b - 1);
	}

	std::vector<int> v = list.sortareTopologica();
	for (auto elem : v) {
		out << elem + 1 << " ";
	}
	out << "\n";

	in.close();
	out.close();
	return 0;
}