Cod sursa(job #1749194)

Utilizator andreioneaAndrei Onea andreionea Data 28 august 2016 01:08:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <fstream>
#include <vector>
#include <unordered_map>
#include <iostream>

struct Node {
	using NodeId = int;
	using NeighborList = std::vector<NodeId>;

	NodeId id = 0;
	NeighborList neighbors;
	int degree = 0;
	Node() {}
	Node(NodeId id) : id(id), degree(0) {}
	Node(const Node& other) : id(other.id) , degree(other.degree) {}
	void AddNeighbor(NodeId neighbor) { neighbors.push_back(neighbor); }
};

struct Graph {
	using NodeList = std::unordered_map<Node::NodeId, Node>;
	using NodeIdList = std::vector<Node::NodeId>;
	NodeList nodes;
	int n;
	Graph(int n) : n(n) {
		for (auto i = 1; i <= n; ++i)
			nodes.insert(std::make_pair(i, Node(i)));
	}
	void AddEdge(Node::NodeId a, Node::NodeId b) {
		auto& nodeA = nodes[a];
		auto& nodeB = nodes[b];
		nodeA.AddNeighbor(b);
		++nodeB.degree;
	}

	NodeIdList SortTopologically() {
		NodeIdList ordered_nodes;
		ordered_nodes.reserve(n);

		for (int i = 1; i <= n; ++i) {
			if (nodes[i].degree == 0) {
				ordered_nodes.push_back(i);
			}
		}

		for (int i = 0; i < n; ++i) {
			auto id = ordered_nodes[i];
			auto& node = nodes[id];
			for (auto neighbor : node.neighbors) {
				auto& neighborNode = nodes[neighbor];
				--neighborNode.degree;
				if (neighborNode.degree == 0) {
					ordered_nodes.push_back(neighborNode.id);
				}
			}
		}
		return ordered_nodes;
	}

};

struct file_manip {

	std::ifstream fin;
	std::ofstream fout;

	file_manip(const char* filename) {
		std::string infilename  = std::string(filename) + ".in";
		std::string outfilename = std::string(filename) + ".out";
		fin.open(infilename.c_str());
		fout.open(outfilename.c_str());
	}

	template <class T>
	file_manip& operator << (const T& rhs) {
		fout << rhs;
		return *this;
	}
	template <class T>
	file_manip& operator >> (T& rhs) {
		fin >> rhs;
		return *this;
	}
};

int main()
{
	file_manip fm("sortaret");
	int n,m;
	fm >> n >> m;
	Graph g(n);
	for (int i = 0; i < m; ++i) {
		Node::NodeId a, b;
		fm >> a >> b;
		g.AddEdge(a,b);
	}
	auto solution = g.SortTopologically();
	for (auto node : solution) {
		fm << node << " ";
	}
	fm << "\n";
	return 0;
}