Pagini recente » Cod sursa (job #502140) | Cod sursa (job #140853) | Cod sursa (job #1866420) | Cod sursa (job #2084174) | Cod sursa (job #2875836)
#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");
signed main() {
int x, y;
in >> n >> m;
for (int i = 1; i <= m; ++i) {
in >> 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;
}
if (!in_degree[nod.first].empty()) {
continue;
}
alreadyChecked[nod.first] = true;
sortTop.emplace_back(nod.first);
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 : sortTop) {
out << it << ' ';
}
return 0;
}