Cod sursa(job #3371574)

Utilizator ursus161Stefan Ghetu ursus161 Data 30 octombrie 2026 21:28:32
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

//cu bfs sortare topologica ii spune algoritmul lui Kahn

std::vector<int> grad;
std::vector<std::vector<int>> graf;
std::queue<int> q;
void topsort(){

    while(!q.empty()){

        int nod  = q.front(); // iau un nod
        q.pop(); fout << nod << " ";

        for (int i : graf[nod]){
            grad[i]--;
            if(!grad[i]){
                
                q.push(i);
            }
            
        }

    }
}

int main(){
    std::ifstream fin("sortaret.in");
    std::ofstream fout("sortaret.out");
    int n, m;
    fin >> n >> m;
    graf.resize(n + 1);
    grad.resize(n + 1, 0);

    for (int i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;
        graf[x].push_back(y); grad[y]++;
    }

    for (size_t i = 1; i < grad.size(); i++)
       if (grad[i] == 0) q.push(i);

    topsort();
}