Pagini recente » preONI 2008 | Cod sursa (job #1271568) | Cod sursa (job #2423830) | Cod sursa (job #602012) | Cod sursa (job #1585274)
#include <fstream>
#include <vector>
#include <queue>
#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, const vector<T>& node)
: nodes(node.begin(), node.end()) {
for (auto& p : pairs) {
edges[p.first].push_back(p.second);
}
}
/**@brief Returns a topological sort of the graph.
*/
vector<T> toposort() {
unordered_map<T, int> in_degree;
for (auto& p : edges) {
for (auto& node : p.second) {
in_degree[node]++;
}
}
vector<T> result;
queue<T> topo;
for (auto& node : nodes) {
if (in_degree[node] == 0)
topo.push(node);
}
while (!topo.empty()) {
auto node = topo.front();
topo.pop();
result.push_back(node);
for (auto& next : edges[node]) {
in_degree[next]--;
if (in_degree[next] == 0) {
topo.push(next);
}
}
}
return result;
}
private:
unordered_map<T, vector<T>> edges;
unordered_set<T> nodes;
};
int main() {
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m; fin >> n >> m;
vector<int> nodes;
for (int i = 0; i < n; ++i) {
nodes.push_back(i + 1);
}
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, nodes);
auto result = g.toposort();
for (auto x : result) {
fout << x << " ";
}
fout << endl;
return 0;
}