Pagini recente » Cod sursa (job #1343684) | Monitorul de evaluare | Cod sursa (job #2968557) | Cod sursa (job #3210185) | Cod sursa (job #1235548)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
void dfs(int node,
std::vector< std::list<int> > &adj,
std::vector<bool> &visited,
std::stack<int> &result)
{
visited[node] = true;
for (auto &i : adj[node])
if (!visited[i])
dfs(i, adj, visited, result);
result.push(node);
}
std::stack<int> sort_topo(std::vector< std::list<int> > &adj,
std::vector<bool> &visited)
{
std::stack<int> result;
for (int i = 0; i < adj.size(); ++i)
if (!visited[i])
dfs(i, adj, visited, result);
return result;
}
int main()
{
std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");
int N, M;
in >> N >> M;
std::vector< std::list<int> > adj(N);
for (int i = 0; i < M; ++i) {
int x, y;
in >> x >> y;
adj[x-1].push_front(y-1);
}
in.close();
std::vector<bool> visited(N, false);
std::stack<int> ordered = sort_topo(adj, visited);
if (ordered.empty())
return 1;
while (!ordered.empty()) {
int vertex = ordered.top();
ordered.pop();
out << vertex+1 << " ";
}
out.close();
return 0;
}