Pagini recente » Cod sursa (job #2295721) | Cod sursa (job #2812332) | Cod sursa (job #910527) | Cod sursa (job #1415821) | Cod sursa (job #2524405)
#include <fstream>
#include <string>
#include <vector>
#include <unordered_set>
const std::string kInputFileName = "sortaret.in";
const std::string kOutputFileName = "sortaret.out";
class TopologicalSorter {
public:
TopologicalSorter(std::vector<std::vector<int>> adj_nodes) :
adj_nodes_(std::move(adj_nodes)) {}
std::vector<int> GetTopologicalSorting() {
for (int node = 0; node < adj_nodes_.size(); node++) {
if (!visited_nodes_.count(node)) {
Dfs(node);
}
}
std::vector<int> top_sorting;
for (int i = adj_nodes_.size() - 1; i >= 0; i--) {
top_sorting.push_back(reversed_top_sorting_[i]);
}
return top_sorting;
}
private:
void Dfs(int node) {
if (visited_nodes_.count(node)) {
return;
}
visited_nodes_.insert(node);
for (const int& adj_node : adj_nodes_[node]) {
Dfs(adj_node);
}
reversed_top_sorting_.push_back(node);
}
const std::vector<std::vector<int>> adj_nodes_;
std::unordered_set<int> visited_nodes_;
std::vector<int> reversed_top_sorting_;
};
int main() {
std::ifstream fin(kInputFileName);
std::ofstream fout(kOutputFileName);
int num_nodes;
fin >> num_nodes;
int num_edges;
fin >> num_edges;
std::vector<std::vector<int>> adj_nodes(num_nodes, std::vector<int>());
for (int i = 0; i < num_edges; i++) {
int start_node;
int end_node;
fin >> start_node >> end_node;
adj_nodes[start_node - 1].push_back(end_node - 1);
}
TopologicalSorter sorter(std::move(adj_nodes));
const auto top_sorting = sorter.GetTopologicalSorting();
for (const int& node : top_sorting) {
fout << node + 1 << ' ';
}
return 0;
}