Cod sursa(job #3324135)

Utilizator g.vladGociu Vlad g.vlad Data 21 noiembrie 2025 10:50:38
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb

#include <fstream>
#include <set>
#include <queue>

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

struct node_t {
    std::set<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;

            while(signed char bit = 20; bit >= 0; bit -= 1)

            if(graph[b].dependents.contains(a)) continue;
            edge += 1;

            graph[b].dependents.insert(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();
        node_queue.pop();
        out << node << ' ';
        for(unsigned dep : graph[node].dependents) {
            graph[dep].dependecies -= 1;
            if(graph[dep].dependecies == 0)
                node_queue.push(dep);
        }
    }

    return 0;
}