Pagini recente » Cod sursa (job #207805) | Cod sursa (job #533050) | Cod sursa (job #3123558) | Cod sursa (job #1057092) | Cod sursa (job #2663516)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <vector>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
class Graph {
int vertices;
list <int> *adj;
public:
Graph() {}
Graph(int len) : vertices(len) {
adj = new list<int>[len + 1];
}
void addEdge(int from, int to) {
adj[from].push_back(to);
}
void depthFirst(int i, vector <bool> &visited, stack <int> &st) {
visited[i] = true;
for (auto &adjVal : adj[i]) {
if (!visited[adjVal])
depthFirst(adjVal, visited, st);
}
st.push(i);
}
void show(stack <int> &st) {
while (true) {
out << st.top();
st.pop();
if (!st.size())
return;
out << " ";
}
}
void topologicalSort() {
stack <int> st;
vector <bool> visited(vertices, false);
for (int i = 1; i <= vertices; ++i) {
if (!visited[i])
depthFirst(i, visited, st);
}
show(st);
}
};
int main() {
int N, M;
in >> N >> M;
Graph *myGraph = new Graph(N);
while (M--) {
int from, to;
in >> from >> to;
myGraph -> addEdge(from, to);
}
myGraph -> topologicalSort();
return 0;
}