Pagini recente » Cod sursa (job #1929866) | Cod sursa (job #179828) | Cod sursa (job #3121107) | Cod sursa (job #1352515) | Cod sursa (job #2059062)
#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) {
stack<int> dfs_stack;
set<int> visited;
vector<int> sorted;
dfs_stack.push(1);
visited.insert(1);
while (!dfs_stack.empty()) {
int current_node = dfs_stack.top();
dfs_stack.pop();
if (!graph[current_node].empty()) {
for (auto node_to_visit : graph[current_node]) {
if (visited.find(node_to_visit) == visited.end()) {
visited.insert(node_to_visit);
dfs_stack.push(node_to_visit);
}
}
}
sorted.push_back(current_node);
}
return sorted;
}
void write_sorted_list(vector<int>& sorted) {
freopen("sortaret.out", "w", stdout);
for (auto node : sorted) {
printf("%d ", node);
}
printf("\n");
fclose(stdout);
}
int main() {
vector<set<int>> graph = read_graph();
vector<int> sorted = toposort(graph);
write_sorted_list(sorted);
return 0;
}