Pagini recente » Cod sursa (job #2777688) | Cod sursa (job #1265621) | Cod sursa (job #3277249) | Cod sursa (job #1566853) | Cod sursa (job #2956857)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
class Graph{
int n, m;
std::vector<std::vector<std::pair<int, int>>> graph;
std::vector<int> father;
std::vector<int> distance;
std::vector<bool> visited;
void dfs(const int k, std::stack<int> &s){
visited[k] = true;
for (int node : getNeighbors(k)){
if (!visited[node]){
father[node] = k;
dfs(node, s);
}
}
s.push(k);
}
public:
explicit Graph(const int n = 0){
this -> n = n;
m = 0;
graph.resize(n+1);
father.resize(n+1);
distance.resize(n+1);
visited.resize(n+1);
}
void addEdge(const int x, const int y, const int cost = 1){
graph[x].push_back({y, cost});
++m;
}
int getEdgeWeight(const int x, const int y) const {
for (const auto& [neighbor, weight] : graph[x]) {
if (neighbor == y) {
return weight;
}
}
return (int)0x80000000;
}
std::vector<int> getNeighbors(const int x) const {
std::vector<int> neighbors;
for (const auto& [neighbor, weight] : graph[x]) {
neighbors.push_back(neighbor);
}
return neighbors;
}
std::vector<std::pair<int, int>> getNeighborsWithWeight(const int x) const {
return graph[x];
}
std::stack<int> topologicalSort() {
std::stack<int> sorted;
visited.assign(n+1, false);
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i, sorted);
}
}
visited.assign(n+1, false);
return sorted;
}
};
int main() {
ifstream in("sortaret.in");
int n, m;
in >> n >> m;
Graph g(n);
while (m--){
int x, y;
in >> x >> y;
g.addEdge(x, y);
}
in.close();
ofstream out("sortaret.out");
stack<int> sorted = g.topologicalSort();
while (!sorted.empty()){
out << sorted.top() << ' ';
sorted.pop();
}
out.close();
return 0;
}