Pagini recente » Cod sursa (job #1777915) | Cod sursa (job #82994) | Cod sursa (job #188036) | Cod sursa (job #2842351) | Cod sursa (job #2294467)
#include <stdio.h>
#include<vector>
#include<stack>
using namespace std;
std::stack<int> topologicalSortUtil(const std::vector<std::vector<int> >& graph, int current,
std::stack<int>& s, std::vector<bool>& visited) {
// Mark the current node as visited
visited[current] = true;
// Recur for all the neighbors to current vertex
for(int i = 0; i < graph[current].size(); i++) {
if(!visited[graph[current][i]]) {
topologicalSortUtil(graph, graph[current][i], s, visited);
}
}
s.push(current);
return s;
}
std::stack<int> topologicalSort(const std::vector<std::vector<int> >& graph) {
stack<int> s;
vector<bool> visited(graph.size(), false);
for(int i = 0; i < graph.size(); i++) {
if(!visited[i]) {
topologicalSortUtil(graph, i, s, visited);
}
}
return s;
}
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int n, m, src, dst;
scanf("%d%d", &n, &m);
std::vector<std::vector<int> > graph(n);
for(int i = 0; i < m; i++) {
scanf("%d%d", &src, &dst);
graph[src - 1].push_back(dst - 1);
}
stack<int> s;
s = topologicalSort(graph);
while(!s.empty()) {
printf("%d ", s.top() + 1);
s.pop();
}
printf("\n");
return 0;
}