Pagini recente » Cod sursa (job #2726456) | Cod sursa (job #2115425) | Cod sursa (job #2485933) | Cod sursa (job #340295) | Cod sursa (job #2510217)
#include <map>
#include <set>
#include <vector>
#include <fstream>
using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
template <typename T>
class Graph {
public:
map<T, set<T>> edges;
void addEdge(T const from, T to) {
edges[from].insert(to);
}
vector<T> topologicSort() {
set<T> vis;
vector<T> ret;
for (auto const & v : edges)
if (vis.find(v.first) == vis.end())
dfs(v.first, vis, ret);
return ret;
}
void dfs(const T&v, set<T>& vis, vector<T>& ret) {
vis.insert(v);
for (auto const & e : edges[v])
if (vis.find(e) == vis.end())
dfs(e, vis, ret);
ret.emplace_back(v);
}
};
int main() {
int Edges;
cin >> Edges;
Graph<int> A;
for (cin >> Edges;Edges!=0; Edges--) {
int from, to;
cin >> from >> to;
A.addEdge(from, to);
}
auto rez = A.topologicSort();
for (auto it : rez)
cout << it << ' ';
}