Pagini recente » Cod sursa (job #3291729) | Rating enache adrian (adyk18) | Cod sursa (job #1562151) | Cod sursa (job #1098446) | Cod sursa (job #1585216)
#include <fstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
/**@brief Generic graph data structure.
*/
template <class T>
class graph {
public:
explicit graph(const vector<pair<T, T>>& pairs) {
for (auto& p : pairs) {
edges[p.first].push_back(p.second);
}
}
/**@brief Returns a topological sort of the graph.
*/
vector<T> toposort() {
unordered_set<T> branch;
for (auto& p : edges) {
for (auto& neigh : p.second)
branch.insert(neigh);
}
vector<T> result;
for (auto& p : edges) {
if (!branch.count(p.first)) {
search(p.first, result);
break;
}
}
return result;
}
private:
void search(T node, vector<T>& result) {
result.push_back(node);
if (!edges[node].empty()) {
for (auto neigh : edges[node]) {
search(neigh, result);
}
}
}
unordered_map<T, vector<T>> edges;
};
int main() {
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m; fin >> n >> m;
vector<pair<int, int>> pairs;
for (int i = 0; i < m; ++i) {
int a, b; fin >> a >> b;
pairs.push_back(pair<int, int>(a, b));
}
graph<int> g(pairs);
auto result = g.toposort();
for (auto x : result) {
fout << x << " ";
}
fout << endl;
return 0;
}