Pagini recente » Cod sursa (job #948456) | Cod sursa (job #753201) | Cod sursa (job #2980260) | Cod sursa (job #2262855) | Cod sursa (job #2061550)
#include <fstream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
class topological_sorter {
private:
int num_nodes;
vector<unordered_set<int>> graph;
vector<bool> visited_nodes;
vector<int> sorted_nodes;
void dfs(int node);
public:
const vector<int>& get_sorted_nodes() const;
void read_graph(string input_file_name);
void sort();
void write_sorted_nodes(string output_file_name);
};
inline const vector<int>& topological_sorter::get_sorted_nodes() const {
return sorted_nodes;
}
void topological_sorter::read_graph(string input_file_name) {
ifstream input_file(input_file_name);
int num_links;
input_file >> num_nodes >> num_links;
vector<unordered_set<int>> tmp_graph(num_nodes + 1);
vector<bool> tmp_visited_nodes(num_nodes);
for (int i = 0; i < num_links; ++i) {
int from, to;
input_file >> from >> to;
tmp_graph[from].insert(to);
}
input_file.close();
graph = tmp_graph;
visited_nodes = tmp_visited_nodes;
}
void topological_sorter::sort() {
for (int node = 1; node <= num_nodes; ++node) {
if (!visited_nodes[node]) {
dfs(node);
}
}
}
void topological_sorter::dfs(int node) {
visited_nodes[node] = true;
for (auto node_it = graph[node].begin(); node_it != graph[node].end(); ++node_it) {
if (!visited_nodes[*node_it]) {
dfs(*node_it);
}
}
sorted_nodes.push_back(node);
}
void topological_sorter::write_sorted_nodes(string output_file_name) {
ofstream output_file(output_file_name);
for (auto node_it = sorted_nodes.rbegin(); node_it != sorted_nodes.rend(); ++node_it) {
output_file << *node_it << ' ';
}
output_file << endl;
output_file.close();
}
int main() {
topological_sorter sorter;
sorter.read_graph("sortaret.in");
sorter.sort();
sorter.write_sorted_nodes("sortaret.out");
return 0;
}