Cod sursa(job #2875836)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 22 martie 2022 13:36:05
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#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;
}