Cod sursa(job #2725850)

Utilizator preda.andreiPreda Andrei preda.andrei Data 19 martie 2021 19:09:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct Node {
    vector<int> edges;
    int indegree = 0;
};

using Graph = vector<Node>;

vector<int> Sort(Graph& graph) {
    vector<int> order;
    order.reserve(graph.size());

    queue<int> q;
    for (size_t i = 0; i < graph.size(); i += 1) {
        if (graph[i].indegree == 0) {
            order.push_back(i);
            q.push(i);
        }
    }

    while (!q.empty()) {
        auto node = q.front();
        q.pop();

        for (const auto& next : graph[node].edges) {
            graph[next].indegree -= 1;
            if (graph[next].indegree == 0) {
                order.push_back(next);
                q.push(next);
            }
        }
    }
    return order;
}

int main() {
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int nodes, edges;
    fin >> nodes >> edges;

    Graph graph(nodes);
    for (auto i = 0; i < edges; i += 1) {
        int a, b;
        fin >> a >> b;
        graph[a - 1].edges.push_back(b - 1);
        graph[b - 1].indegree += 1;
    }

    auto order = Sort(graph);
    for (const auto& node : order) {
        fout << node + 1 << " ";
    }
    fout << "\n";

    return 0;
}