Cod sursa(job #2962113)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 7 ianuarie 2023 19:28:45
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <vector>
#include <queue>

int n, m;
std::vector<std::vector<int>> G;
std::queue<int> q;
std::vector<int> deg, sol;

void read_data(){
    int u, v;
    scanf("%d%d", &n, &m);

    deg = std::vector<int>(n, 0);
    G = std::vector<std::vector<int>>(n);

    for(int i = 0; i < m; i ++){
        scanf("%d%d", &u, &v);
        G[u - 1].push_back(v - 1);
        deg[v - 1] ++;
    }
}

void solve(){
    int u, v;

    for(int i = 0; i < n; i ++)
        if(deg[i] == 0)
            q.push(i);
    
    while(!q.empty()){
        u = q.front();
        q.pop();
        sol.push_back(u);

        for(const int& v: G[u]){
            deg[v] --;
            if(deg[v] == 0)
                q.push(v);
        }
    }   
}

void write_data(){
    for(int i = 0; i < sol.size(); i ++)
        printf("%d ", sol[i] + 1);
    printf("\n");
}

int main(){
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}