Pagini recente » Cod sursa (job #1964253) | Cod sursa (job #3200352) | Cod sursa (job #2546936) | Cod sursa (job #1440754) | Cod sursa (job #1749194)
#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;
}