Pagini recente » Cod sursa (job #1351907) | Cod sursa (job #179169) | Cod sursa (job #2223632)
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef vector<vector<int>> Graph;
const string IN_FILE = "sortaret.in";
const string OUT_FILE = "sortaret.out";
void dfs(
const Graph& graph,
const int u,
vector<bool>& visited,
vector<int>& order) {
visited[u] = true;
for (const auto& v : graph[u]) {
if (!visited[v]) {
dfs(graph, v, visited, order);
}
}
order.push_back(u);
}
vector<int> getTopologicalOrder(const Graph& graph) {
auto visited = vector<bool>(int(graph.size()));
auto order = vector<int>();
for (int u = 0; u < int(graph.size()); u++) {
if (!visited[u]) {
dfs(graph, u, visited, order);
}
}
reverse(order.begin(), order.end());
return order;
}
Graph readGraph() {
ifstream in(IN_FILE);
int V, E;
in >> V >> E;
auto graph = Graph(V);
for (int i = 0; i < E; i++) {
int u, v;
in >> u >> v;
graph[u - 1].push_back(v - 1);
}
in.close();
return graph;
}
void writeOutput(const vector<int>& order) {
ofstream out(OUT_FILE);
for (int i = 0; i < int(order.size()); i++) {
out << order[i] + 1 << (i + 1 < int(order.size()) ? " " : "\n");
}
out.close();
}
int main() {
const auto graph = readGraph();
const auto order = getTopologicalOrder(graph);
writeOutput(order);
return 0;
}