Cod sursa(job #1053000)

Utilizator sunt_emoSunt emo sunt_emo Data 12 decembrie 2013 00:27:34
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <queue>

int n, m;

std::map<int, std::vector<int> > graph;
std::map<int, int> ext;

std::queue<int> good;
std::vector<int> res;

void read()
{
    std::ifstream in("sortaret.in");
    in >> n >> m;
    for (int i = 0; i < n; i++)
    {
        graph.insert(std::make_pair(i + 1, std::vector<int>()));
        ext.insert(std::make_pair(i + 1, 0));
    }
    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        std::pair<std::map<int, std::vector<int> >::iterator, bool> ret = graph.insert(std::make_pair(x, std::vector<int>()));
        ret.first->second.push_back(y);
        std::pair<std::map<int, int>::iterator, bool> ret2 = ext.insert(std::make_pair(y, 0));
        ret2.first->second++;
        ext.insert(std::make_pair(x, 0));
    }
    for (std::map<int, int>::iterator it = ext.begin(); it != ext.end(); ++it)
        if (it->second == 0)
            good.push(it->first);
    in.close();
}

void solve()
{
    while (!good.empty())
    {
        int k = good.front();
        good.pop();
        res.push_back(k);
        std::map<int, std::vector<int> >::iterator it = graph.find(k);
        for (std::vector<int>::iterator it2 = it->second.begin(); it2 != it->second.end(); ++it2)
        {
            std::map<int, int>::iterator it3 = ext.find(*it2);
            it3->second--;
            if (it3->second == 0)
                good.push(it3->first);
        }
    }
}

void write()
{
    std::ofstream out("sortaret.out");
    for (std::vector<int>::iterator it = res.begin(); it != res.end(); ++it)
        out << *it << " ";
    out << std::endl;
    out.close();
}

int main()
{
    read();
    solve();
    write();
}