Cod sursa(job #3324127)

Utilizator g.vladGociu Vlad g.vlad Data 21 noiembrie 2025 10:27:09
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb

#include <fstream>
#include <vector>
#include <queue>

std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");

struct node_t {
    std::vector<unsigned> dependents;
    unsigned dependecies = 0;
};

int main()
{
    unsigned nodes, edges;
    node_t graph[50001];
    std::queue<unsigned> node_queue;

    in >> nodes >> edges;

    {
        unsigned a, b, edge = 0;
        bool found;
        while(edge < edges) {
            in >> b >> a;
            found = false;
            for(unsigned const& dep : graph[b].dependents) {
                if(dep == a) {
                    found = true;
                    break;
                }
            }
            if(found) continue;
            edge += 1;

            graph[b].dependents.push_back(a);
            graph[a].dependecies += 1;
        }
    }

    for(unsigned node = 1; node <= nodes; node += 1) {
        if(graph[node].dependecies == 0)
            node_queue.push(node);
    }

    while(!node_queue.empty()) {
        unsigned node = node_queue.front();
        out << node << ' ';
        for(unsigned dep : graph[node].dependents) {
            if(graph[dep].dependecies == 0) continue;
            graph[dep].dependecies -= 1;
            if(graph[dep].dependecies == 0)
                node_queue.push(dep);
        }
        node_queue.pop();
    }

    return 0;
}