Cod sursa(job #2844087)

Utilizator icnsrNicula Ionut icnsr Data 3 februarie 2022 18:57:19
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <vector>
#include <queue>

static int N, M;
static std::vector<std::vector<int>> adj;
static std::vector<int> in_degree;

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

        scanf("%d %d", &N, &M);

        adj.resize(N + 1);
        in_degree.resize(N + 1);

        for(int i = 0; i < M; ++i)
        {
                int u, v;
                scanf("%d %d", &u, &v);

                adj[u].push_back(v);
                ++in_degree[v];
        }

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

        while(!q.empty())
        {
                const int u = q.front();
                q.pop();

                printf("%d ", u);

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

        puts("");
}