Cod sursa(job #2803389)

Utilizator icnsrNicula Ionut icnsr Data 19 noiembrie 2021 22:28:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <vector>
#include <queue>

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

        int N, M;
        std::cin >> N >> M;

        std::vector<int> deg(N + 1, 0);
        std::vector<std::vector<int>> adj(N + 1);
        for(int i = 0; i < M; ++i)
        {
                int x, y;
                std::cin >> x >> y;

                adj[x].push_back(y);
                ++deg[y];
        }

        std::queue<int> q;
        for(int i = 1; i <= N; ++i)
        {
                if(deg[i] == 0)
                {
                        q.push(i);
                }
        }

        for(int i = 0; i < N; ++i)
        {
                const auto current = q.front();
                q.pop();

                printf("%d ", current);
                for(int neigh : adj[current])
                {
                        --deg[neigh];
                        if(deg[neigh] == 0)
                        {
                                q.push(neigh);
                        }
                }
        }

        puts("");
}