Cod sursa(job #2844086)

Utilizator icnsrNicula Ionut icnsr Data 3 februarie 2022 18:56:36
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 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()
{
        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);
                }
        }

        std::vector<char> visited(N + 1, false);
        while(!q.empty())
        {
                const int u = q.front();
                q.pop();
                visited[u] = true;

                printf("%d ", u);

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

        puts("");
}