Cod sursa(job #2247029)

Utilizator preda.andreiPreda Andrei preda.andrei Data 27 septembrie 2018 19:47:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>

using namespace std;

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

using Graph = vector<Node>;

vector<int> FindOrder(Graph &graph)
{
    vector<int> order(graph.size());
    auto left = 0, right = 0;

    for (size_t i = 0; i < graph.size(); i += 1) {
        if (graph[i].indegree == 0) {
            order[right] = i;
            right += 1;
        }
    }

    while (right < (int)order.size()) {
        auto node = order[left];
        left += 1;

        for (const auto &other : graph[node].edges) {
            graph[other].indegree -= 1;
            if (graph[other].indegree == 0) {
                order[right] = other;
                right += 1;
            }
        }
    }
    return order;
}

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

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

    Graph graph(nodes);
    for (int i = 0; i < edges; i += 1) {
        int x, y;
        fin >> x >> y;

        graph[x - 1].edges.push_back(y - 1);
        graph[y - 1].indegree += 1;
    }

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

    return 0;
}