Cod sursa(job #2506052)

Utilizator vxpsnVictor Pusnei vxpsn Data 7 decembrie 2019 13:29:23
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;
typedef unsigned long long ull;

const ll nmx = 5e4 + 5;

int main() {
    ios::sync_with_stdio(0);

    ll N, M, g[nmx] = {};
    vector <ll> l[nmx], ans;
    bitset <nmx> vis;
    queue <ll> q;

    in>>N>>M;

    for(int i = 1; i <= M; ++i) {
        ll x, y;
        in>>x>>y;
        l[x].push_back(y);
        g[y]++;
    }

    for(int i = 1; i <= N; ++i) {
        if(g[i] == 0) {
            q.push(i);
            vis[i] = 1;
        }
    }

    while(!q.empty()) {
        ll f = q.front();
        q.pop();

        ans.push_back(f);

        for(auto k : l[f]) {
            --g[k];
            if(g[k] == 0) {
                q.push(k);
                vis[k] = 1;
            }
        }
    }

    for(auto k : ans) out<<k<<" ";

    return 0;
}