Pagini recente » Dag | Nrcuv 1 | Monitorul de evaluare | Turnuri4 | Cod sursa (job #2843670)
#include "pch.h"
//#include <bits/stdc++.h>
using namespace std;
ifstream fin("topsort.in");
ofstream fout("topsort.out");
const int N_MAX = 50000;
vector<int> v[N_MAX + 1];
int exteriorGrade[N_MAX + 1];
void topologicalSort(vector<int>& q, const int& n) {
q.reserve(n);
for (int i = 1; i <= n; ++i) {
if (!exteriorGrade[i]) {
q.push_back(i);
}
}
for (int i = 0; i < n; ++i) {
for (const int& index : v[q[i]]) {
if (!--exteriorGrade[index])
q.push_back(index);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
while (m--) {
int x, y;
cin >> x >> y;
v[x].push_back(y);
++exteriorGrade[y];
}
vector<int> q;
topologicalSort(q, n);
for (const int& x : q) {
cout << x << ' ';
}
}