Pagini recente » Cod sursa (job #2864117) | Cod sursa (job #325100) | Cod sursa (job #2405523) | Cod sursa (job #668382) | Cod sursa (job #3265677)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <algorithm>
class Graf_orientat {
private:
std::vector<std::vector<int>> L; // Adjacency list
std::vector<int> vis; // Visited array for DFS
int num_nodes; // Number of nodes
public:
explicit Graf_orientat(int num_nodes) : num_nodes(num_nodes) {
L.resize(num_nodes + 1);
vis.resize(num_nodes + 1, 0);
}
void add_edge(int u, int v) {
L[u].push_back(v);
}
void dfs(int node, std::vector<int>& top_order) {
vis[node] = 1;
for (auto next : L[node]) {
if (!vis[next]) {
dfs(next, top_order);
}
}
top_order.push_back(node);
}
std::vector<int> sortare_topologica() {
std::vector<int> top_order;
for (int i = 1; i <= num_nodes; ++i) {
if (!vis[i]) {
dfs(i, top_order);
}
}
std::reverse(top_order.begin(), top_order.end());
return top_order;
}
};
int main() {
std::ifstream infile("sortaret.in");
std::ofstream outfile("sortaret.out");
if (!infile.is_open() || !outfile.is_open()) {
std::cerr << "Error opening input or output file." << std::endl;
return 1;
}
int N, M;
infile >> N >> M;
Graf_orientat g(N);
for (int i = 0; i < M; ++i) {
int X, Y;
infile >> X >> Y;
g.add_edge(X, Y);
}
std::vector<int> topo_sort = g.sortare_topologica();
for (size_t i = 0; i < topo_sort.size(); ++i) {
if (i > 0) {
outfile << " ";
}
outfile << topo_sort[i];
}
outfile << std::endl;
infile.close();
outfile.close();
return 0;
}