Cod sursa(job #2875600)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 21 martie 2022 23:22:30
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
#include <chrono>

using namespace std;
const int NR = 1e5 + 10;

vector<int> in_degree[NR];
vector<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].emplace_back(y);
        in_degree[y].emplace_back(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 (alreadyChecked[nod]) {
            continue;
        }
        alreadyChecked[nod] = true;
        sortTop.emplace_back(nod);
        for (auto it : out_degree[nod]) {
            zero[it]--;
            if (!zero[it]) {
                que.emplace_back(it);
            }
        }
    }
    for (auto it : sortTop) {
        out << it << ' ';
    }
    return 0;
}