Cod sursa(job #2875596)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 21 martie 2022 23:14:55
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 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];

vector<int> que;
vector<int> sortTop;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector<int> zero(NR, 0);

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);
        zero[y]++;
    }
    for (int i = 1; i <= n; ++i) {
        if (!zero[i]) {
            que.emplace_back(i);
        }
    }
    while (!que.empty()) {
        int nod = que.back();
        que.pop_back();
        if (!in_degree[nod].empty()) {
            cout << "oh no\n";
            exit(0);
        }
        sortTop.emplace_back(nod);
        for (auto it : out_degree[nod]) {
            in_degree[it].erase(nod);
            if (in_degree[it].empty()) {
                que.emplace_back(it);
            }
        }
    }
    for (auto it : sortTop) {
        out << it << ' ';
    }
    return 0;
}