Pagini recente » Cod sursa (job #2393233) | Cod sursa (job #2397431) | Cod sursa (job #1888866) | Cod sursa (job #1460828) | Cod sursa (job #1847590)
#include <bits/stdc++.h>
using namespace std;
struct TopoSort {
vector< vector<int> >& edges;
vector<int> sorted;
vector<bool> visited;
int V, s_ix;
TopoSort(vector< vector<int> >& edges) :
edges(edges), V((int) edges.size()), s_ix((int) edges.size()),
sorted((int) edges.size(), -1), visited((int) edges.size(), false) {}
void visit(int u) {
visited[u] = true;
for (int v : edges[u]) {
if (!visited[v]) {
visit(v);
}
}
sorted[--s_ix] = u;
}
void sort() {
for (int i = 0; i < V; i++) {
if (!visited[i]) {
visit(i);
}
}
}
};
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int n, m;
scanf("%d %d", &n, &m);
vector< vector<int> > edges(n, vector<int>());
for (int i = 0; i < m; i++) {
int x, y;
scanf("%d %d", &x, &y);
x--, y--;
edges[x].push_back(y);
}
TopoSort topo_sort(edges);
topo_sort.sort();
for (int i : topo_sort.sorted) {
printf("%d ", i + 1);
}
puts("");
return 0;
}