Cod sursa(job #1416548)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 8 aprilie 2015 13:19:03
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <unordered_set>

using AdjList = std::vector<std::list<int>>;

std::queue<int> noIncomingEdges(const AdjList &in_list)
{
    std::queue<int> ret_list;

    for (auto it = in_list.cbegin(); it != in_list.cend(); ++it)
        if (it->empty())
            ret_list.push(it - in_list.cbegin());

    return ret_list;
}

std::list<int> sorttopo(AdjList &in_list, const AdjList &out_list)
{
    auto no_inc_edges = noIncomingEdges(in_list);
    std::list<int> ret_list;

    while (!no_inc_edges.empty()) {
        auto vertex = no_inc_edges.front();
        no_inc_edges.pop();

        ret_list.push_back(vertex);
        for (auto it = out_list[vertex].cbegin(); it != out_list[vertex].cend();
            ++it) {
            in_list[*it].remove(vertex);
            if (in_list[*it].empty())
                no_inc_edges.push(*it);
        }
    }

    return !in_list.front().empty() ? std::list<int>{} : ret_list;
}

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

    int N, M;
    in >> N >> M;

    AdjList in_list(N);
    AdjList out_list(N);
    for (auto i = 0; i < M; ++i) {
        int x, y;
        in >> x >> y;

        in_list[y - 1].push_front(x - 1);
        out_list[x - 1].push_front(y - 1);
    }

    for (auto i = 0; i < N; ++i) {
        in_list[i].unique();
        out_list[i].unique();
    }

    auto ordered = sorttopo(in_list, out_list);
    if (ordered.empty()) {
        std::cerr << "Graph has cycles!" << std::endl;
        return 1;
    }

    for (auto &i : ordered)
        out << i + 1 << " ";

    return 0;
}