Cod sursa(job #944591)

Utilizator sebii_cSebastian Claici sebii_c Data 29 aprilie 2013 02:36:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

class graph {
 public:
     explicit graph(int _size)
         : size(_size),
           edges(_size) {}

     void add_edge(int src, int dst) {
        edges[src].push_back(dst);
     }

     std::vector<int> topological_sort() {
        std::vector<int> in_degree(size);
        for (auto i = 0; i < size; ++i)
            for (auto neighbour : edges[i])
                ++in_degree[neighbour];

        std::queue<int> q;
        for (auto i = 0; i < size; ++i)
            if (in_degree[i] == 0)
                q.push(i);

        std::vector<int> result;
        while (!q.empty()) {
            int node = q.front();
            q.pop();

            result.push_back(node);

            for (auto neighbour : edges[node]) {
                --in_degree[neighbour];
                if (in_degree[neighbour] == 0)
                    q.push(neighbour);
            }
        }

        return result;
     }
 
 private:
     int size;
     std::vector<std::vector<int>> edges;
};

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

    int N, M;
    fin >> N >> M;

    graph g(N);
    for (int i = 0; i < M; ++i) {
        int src, dst;
        fin >> src >> dst;
        --src, --dst;
        g.add_edge(src, dst);
    }

    auto result = g.topological_sort();
    for (auto node : result)
        fout << ++node << " ";
    fout << "\n";

    return 0;
}