Cod sursa(job #1234975)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 28 septembrie 2014 14:28:18
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>


std::queue<int> noIncomingEdges(const std::vector< std::list<int> > &in_list)
{
    std::queue<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(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::queue<int> no_inc_edges = noIncomingEdges(in_list);

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

        ret_list.push_back(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(*it);
        }
    }

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

    return ret_list;
}

bool equal(int a, int b)
{
    return a == b;
}

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);
    std::vector< std::list<int> > out_list(N);
    std::vector< std::vector<bool> > added_out(N);

    for (std::vector< std::vector<bool> >::iterator it = added_out.begin();
         it != added_out.end(); ++it) {
        it->reserve(N);
        it->insert(it->begin(), N, false);
    }

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

        in_list[y-1].push_front(x-1);
        if (!added_out[x-1][y-1]) {
            out_list[x-1].push_front(y-1);
            added_out[x-1][y-1] = true;
        }
    }
    in.close();

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

    out.close();
    return 0;
}