Cod sursa(job #947010)

Utilizator BitOneSAlexandru BitOne Data 6 mai 2013 15:33:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>

using namespace std;

const int NMAX = 50011;

int inD[NMAX];
bool was[NMAX];
vector<int> dfs;
vector<int> G[NMAX];

int main()
{
    int N, M, x, y, i;
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");

    for(in >> N >> M; M; --M)
    {
        in >> x >> y;
        G[x].push_back(y);
        ++inD[y];
    }
    dfs.reserve(N);
    for(i = 1; i <= N; ++i)
    {
        if(!inD[i])
        {
            dfs.push_back(i);
        }
    }
    for(i = 1; dfs.size() < N; ++i)
    {
        x = dfs[i - 1];
        for(auto& y : G[x])
        {
            --inD[y];
            if(!inD[y])
            {
                dfs.push_back(y);
            }
        }
    }

    copy(dfs.begin(), dfs.end(), ostream_iterator<int>(out, " "));
    out << '\n';

    return EXIT_SUCCESS;
}