Pagini recente » Cod sursa (job #2483913) | Cod sursa (job #434836) | Cod sursa (job #590183) | Cod sursa (job #72254) | Cod sursa (job #1839301)
#include <bits/stdc++.h>
using namespace std;
#define SIZE(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
typedef long long int64; typedef unsigned long long uint64;
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
struct TopologicalSort { // 0 - indexed
vector<vector<int>>& g;
vector<bool> visited;
vector<int> sorted;
int V, s_ix;
TopologicalSort(vector<vector<int>>& g) :
g(g), V(g.size()), s_ix((int) g.size()),
sorted(g.size(), -1), visited(g.size(), false) {}
void visit(int u) {
visited[u] = true;
for (int v : g[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>> g(N, vector<int>());
for (int i = 0; i < M; i++) {
int x, y;
scanf("%d %d", &x, &y);
x--, y--;
g[x].push_back(y);
}
TopologicalSort top(g);
top.sort();
vector<int>& ret = top.sorted;
int num = 0;
for (int i : ret) {
if (num++) printf(" ");
printf("%d", i + 1);
}
return 0;
}