Cod sursa(job #2859169)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 28 februarie 2022 22:20:39
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
 
using namespace std;
 
inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}
 
void solve() {
    int n, m; cin >> n >> m;
    vector <vector <int>> adj(n + 1);
    vector <int> gi(n + 1);
    while(m--) {
        int a, b; cin >> a >> b;
        adj[a].emplace_back(b);
        ++gi[b];
    }

    queue <int> q;
    vector <int> sol;
    for(int i = 1;i <= n;i++)
        if(gi[i] == 0) {
            q.emplace(i);
        }

    while(!q.empty()) {
        int v = q.front();
        sol.emplace_back(v);
        q.pop();

        for(int u : adj[v]) {
            if(--gi[u] == 0) {
                q.emplace(u);
            }
        }
    }

    for(auto& it : sol)
        cout << it << " ";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    Open("sortaret");
 
    int T = 1;
    for(;T;T--) {
        solve();
    }
 
    return 0;
}