Cod sursa(job #1053002)

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

#define N 50010

int n, m, ext[N];

std::queue<int> good;
std::vector<int> res, graph[N];

void read()
{
    std::ifstream in("sortaret.in");
    in >> n >> m;
    for (int i = 1; i <= n; i++)
        ext[i] = 0;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        graph[x].push_back(y);
        ext[y]++;
    }
    for (int i = 1; i <= n; i++)
        if (ext[i] == 0)
            good.push(i);
    in.close();
}

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

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();
}