Pagini recente » Cod sursa (job #2901005) | Istoria paginii runda/muntele_suferintei_1 | Cod sursa (job #2203152) | Cod sursa (job #1921855) | Cod sursa (job #3138982)
#include <fstream>
#include <vector>
#include <stack>
using Graph = std::vector<std::vector<int>>;
void dfs(Graph& g, std::stack<int>& s, int node) {
g[0][node - 1] = 1;
if (g[node].empty()) {
s.push(node);
return ;
}
for(const auto& x: g[node]) {
if (!g[0][x - 1]) {
dfs(g, s, x);
}
}
s.push(node);
}
int main() {
std::ifstream in{ "sortaret.in" };
int N, M;
Graph g;
in >> N >> M;
g.reserve(N + 1);
for (int i = 0; i < M; ++i) {
int x, y;
in >> x >> y;
g[x].emplace_back(y);
}
g[0] = std::vector<int>(N, 0);
std::stack<int> s;
for (int i = 0; i < N; ++i) {
if (!g[0][i]) {
dfs(g, s, i + 1);
}
}
std::ofstream out{"sortaret.out"};
for(; !s.empty(); s.pop()) {
out << s.top() << ' ';
}
return 0;
}