Pagini recente » Cod sursa (job #2533620) | Cod sursa (job #157507) | Cod sursa (job #1769078) | Cod sursa (job #3150381) | Cod sursa (job #3183856)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 100000;
int N, M;
int in_degree[MAX + 3];
int T[MAX + 3], k;
int v[MAX + 3];
vector<int>G[MAX + 3];
queue<int>q;
int X, Y;
void topo() {
for(int i = 1; i <= N; i++) {
for(auto j : G[i]) {
in_degree[j]++;
}
}
for(int i = 1; i <= N; i++) {
if(in_degree[i] == 0)
q.push(i);
}
while(!q.empty()) {
T[++k] = q.front();
for(auto i : G[q.front()]) {
in_degree[i]--;
if(in_degree[i] == 0 && !v[i]) {
v[i] = 1;
q.push(i);
}
}
q.pop();
}
}
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
cin >> N >> M;
for(int i = 1; i <= M; i++) {
cin >> X >> Y;
G[X].push_back(Y);
}
topo();
for(int i = 1; i <= N; i++) {
cout << T[i] << ' ';
}
}