Cod sursa(job #1234247)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 26 septembrie 2014 22:34:51
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>


std::list<int> noIncomingEdges(const std::vector< std::list<int> > &in_list)
{
    std::list<int> ret_list;

    for (std::vector< std::list<int> >::const_iterator it = in_list.cbegin();
         it != in_list.cend(); ++it)
        if (it->empty())
            ret_list.push_front(it - in_list.cbegin());

    return ret_list;
}

std::list<int> sorttopo(std::vector< std::list<int> > &in_list,
                        std::vector< std::list<int> > &out_list)
{
    std::list<int> no_inc_edges = noIncomingEdges(in_list);

    std::list<int> ret_list;
    while (!no_inc_edges.empty()) {
        int vertex = no_inc_edges.back();
        no_inc_edges.pop_back();

        ret_list.push_front(vertex);
        for (std::list<int>::const_iterator 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_front(*it);
        }
    }

    if (!in_list.front().empty()) {
        std::cerr << "Graph has cycles!" << std::endl;
        return std::list<int>();
    }

    return ret_list;
}

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

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

    std::vector< std::list<int> > in_list(N+1);
    std::vector< std::list<int> > out_list(N+1);

    for (int i = 0; i < M; ++i) {
        int x, y;
        in >> x >> y;

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

    std::list<int> ordered = sorttopo(in_list, out_list);
    for (auto i : ordered)
        out << i+1 << " ";

    out.close();
    return 0;
}