Cod sursa(job #3208830)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 1 martie 2024 10:26:07
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#warning sunt pe onlinegdb

using namespace std;

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

const int nmax = 50000;
vector<int> g[5 + nmax];
int fr[5 + nmax];

void toposort(int n) {
    queue<int> que;
    for (int i = 1; i <= n; i++) {
        if (fr[i] == 0) {
            que.push(i);
        }
    }
    while (!que.empty()) {
        int node = que.front();
        que.pop();
        fout << node << ' ';
        for (int son : g[node]) {
            fr[son]--;
            if (fr[son] == 0) {
                que.push(son);
            }
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    while (m--) {
        int u, v;
        fin >> u >> v;
        g[u].push_back(v);
        fr[v]++;
    }
    toposort(n);
    fout << '\n';
    return 0;
}