Cod sursa(job #894445)

Utilizator SPDionisSpinei Dionis SPDionis Data 26 februarie 2013 21:23:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <cstdlib>

using std::vector;
using std::cout;
using std::endl;
std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");
const int NMAX = 50010;



int main()
{
    int N,M;
    in >> N >> M;
    vector<int> gr(N + 1);
    vector< vector<int> > graf;
    graf.resize(N + 1);

    for (int i = 0; i < M; ++i)
    {
        int a,b; in >> a >> b;
        graf[a].push_back(b); gr[b]++;
    }

    vector<int> rez;
    for (int i = 1; i <= N; ++i)
        if ( gr[i] == 0 ) rez.push_back(i);


    for (int i = 0; i < N; ++i)
    {
        int x = rez[i];
        for (int it = 0; it < graf[x].size(); it++) {
            gr[ graf[x][it] ]--; if ( !gr[ graf[x][it] ] )  rez.push_back( graf[x][it] );
        }
    }

    for (int i = 0; i < rez.size(); ++i)
        out << rez[i] << " ";
    out.close();
    in.close();
    return 0;
}