Pagini recente » Cod sursa (job #2881029) | Cod sursa (job #2319791) | Cod sursa (job #1311738) | Cod sursa (job #1549264) | Cod sursa (job #2875842)
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
const int NR = 1e5 + 10;
set<int> in_degree[NR];
set<int> out_degree[NR];
int n, m;
bool alreadyChecked[NR];
struct cmp {
bool inline operator()(const pair<int, int> i, const pair<int, int> j) {
return i.second > j.second;
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
vector<int> sortTop;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector<pair<int, int>> edges;
vector<int> posInTopSort(NR, 0);
signed main() {
ios::sync_with_stdio(false);
in.tie(nullptr);
int x, y;
in >> n >> m;
for (int i = 1; i <= m; ++i) {
in >> x >> y;
edges.emplace_back(x, y);
out_degree[x].insert(y);
in_degree[y].insert(x);
}
for (int i = 1; i <= n; ++i) {
pq.push(make_pair(i, in_degree[i].size()));
}
while (!pq.empty()) {
auto nod = pq.top();
pq.pop();
if (alreadyChecked[nod.first] || nod.second != in_degree[nod.first].size()) {
continue;
}
alreadyChecked[nod.first] = true;
sortTop.emplace_back(nod.first);
posInTopSort[nod.first] = sortTop.size() - 1;
for (auto it : out_degree[nod.first]) {
in_degree[it].erase(nod.first);
if (in_degree[it].empty()) {
pq.push(make_pair(it, in_degree[it].size()));
}
}
}
/*
for (auto it : edges) {
if (posInTopSort[it.second] <= posInTopSort[it.first]) {
cout << "NO\n";
return 0;
}
}
*/
for (auto it : sortTop) {
out << it << ' ';
}
return 0;
}