Cod sursa(job #1052999)

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

#define N 50010

int n, m;

std::vector<int> graph[N];
int ext[N];

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++)
        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 it2 = graph[k].begin(); it2 != graph[k].end(); ++it2)
        {
            ext[*it2]--;
            if (ext[*it2] == 0)
                good.push(*it2);
        }
    }
}

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