Pagini recente » Cod sursa (job #159144) | Cod sursa (job #1197952) | Cod sursa (job #279757) | Cod sursa (job #1488742) | Cod sursa (job #2431723)
#include <fstream>
#include <assert.h>
#include <stack>
#include <vector>
#include <iterator>
#include <iostream>
std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");
void dfs(int src, std::vector<bool> &visited, std::vector<std::vector<int>> matrix, std::stack<int> &stack) {
visited[src] = true;
for (auto it = matrix[src].begin(); it != matrix[src].end(); ++it) {
if (!visited[*it]) {
visited[*it] = true;
dfs(*it, visited, matrix, stack);
}
}
stack.push(src);
}
int main() {
int n, m, src, dest;
std::stack<int> stack;
in >> n >> m;
assert(1 <= n && n <= 50000);
assert(1 <= m && m <= 100000);
std::vector<bool> visited(n + 1, false);
std::vector<std::vector<int>> matrix (n + 1, std::vector<int>(n + 1));
for(; m ; --m) {
in >> src >> dest;
matrix[src].push_back(dest);
}
for (int i = 1 ; i <= n ; ++i) {
if (!visited[i]) {
dfs(i, visited, matrix, stack);
}
}
while (!stack.empty()) {
int node = stack.top();
stack.pop();
if (node) out << node << " ";
}
in.close();
out.close();
return 0;
}