Cod sursa(job #3337770)

Utilizator Alex283810Mocan Alexandru Vali Alex283810 Data 29 ianuarie 2026 21:43:38
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
int main() {

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

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>>muchii(n + 1);
    std::vector<int>dependente(n + 1, 0);
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        std::cin >> a >> b;
        muchii[a].push_back(b);
        dependente[b]++;
    }
    std::vector<int>sortat;
    std::queue<int>q;
    for(int i = 1; i <= n; i++)
    {
        if(dependente[i] == 0){
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int curr = q.front();
        q.pop();
        sortat.push_back(curr);
        for(auto vecini : muchii[curr])
        {
            dependente[vecini]--;
            if(dependente[vecini] == 0)
                q.push(vecini);
        }
    }
    for(auto nod : sortat)
        std::cout << nod << ' ';
    return 0;
}