Pagini recente » Cod sursa (job #887649) | Cod sursa (job #61410) | Cod sursa (job #2723801) | Cod sursa (job #1116112) | Cod sursa (job #2060634)
#include <cstdio>
#include <set>
#include <stack>
#include <vector>
using namespace std;
vector<set<int>> read_graph() {
freopen("sortaret.in", "r", stdin);
int num_nodes, num_links;
scanf("%d %d", &num_nodes, &num_links);
vector<set<int>> graph(num_nodes + 1);
for (int i = 0; i < num_links; ++i) {
int from, to;
scanf("%d %d", &from, &to);
graph[from].insert(to);
}
fclose(stdin);
return graph;
}
vector<int> toposort(vector<set<int>>& graph) {
set<int> visited;
vector<int> sorted;
for (int node = 1; node < graph.size(); ++node) {
if (visited.find(node) != visited.end()) {
continue;
}
stack<int> dfs_stack;
stack<int> dfs_full_stack;
dfs_stack.push(node);
while (!dfs_stack.empty()) {
int current_node = dfs_stack.top();
visited.insert(current_node);
dfs_full_stack.push(current_node);
dfs_stack.pop();
for (auto node_to_visit_it = graph[current_node].begin();
node_to_visit_it != graph[current_node].end();
++node_to_visit_it) {
if (visited.find(*node_to_visit_it) == visited.end()) {
dfs_stack.push(*node_to_visit_it);
visited.insert(*node_to_visit_it);
}
}
}
while (!dfs_full_stack.empty()) {
sorted.push_back(dfs_full_stack.top());
dfs_full_stack.pop();
}
}
return sorted;
}
void write_sorted_list(vector<int>& sorted) {
freopen("sortaret.out", "w", stdout);
for (auto node_rit = sorted.rbegin(); node_rit != sorted.rend(); ++node_rit) {
printf("%d ", *node_rit);
}
printf("\n");
fclose(stdout);
}
int main() {
vector<set<int>> graph = read_graph();
vector<int> sorted = toposort(graph);
write_sorted_list(sorted);
return 0;
}