Cod sursa(job #2777699)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 23 septembrie 2021 22:06:44
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
#include <queue>

std::ifstream fin ("sortaret.in");
std::ofstream fout ("sortaret.out");

int const nmax = 50000;
int conexiuni[nmax + 5];
std::vector <std::vector <int>> adj;
std::queue <int> q;

int main() {
    int n, m;
    fin >> n >> m;
    adj.resize(n + 1);
    for (int i = m; i; i--) {
        int x, y;
        fin >> x >> y;
        conexiuni[y]++;
        adj[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
        if (conexiuni[i] == 0)
            q.push(i);
    while (!q.empty()) {
        int top = q.front();
        q.pop();
        fout << top << " ";
        int cnt = adj[top].size();
        for (int i = 0; i < cnt; i++) {
            conexiuni[adj[top][i]]--;
            if (conexiuni[adj[top][i]] == 0)
                q.push(adj[top][i]);
        }
    }
    return 0;
}