Cod sursa(job #1204871)

Utilizator mvcl3Marian Iacob mvcl3 Data 4 iulie 2014 12:31:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <stack>

#define in "sortaret.in"
#define out "sortaret.out"
#define Max_N 50001

std :: ifstream f(in);
std :: ofstream g(out);

class SortareTopologica
{
    protected :
        int N, M;
        bool Viz[Max_N];
        std :: vector < int > V[Max_N];
        std :: stack < int >  my_stack;

    public :
        void Read();
        void Init();
        void TopologicSort();
        void DF(int);
        void Write();
};

void SortareTopologica :: Init()
{
    for(int i = 1; i <= N; ++i) V[i].clear();
    memset(Viz, 0, sizeof(Viz));
    while(!my_stack.empty())    my_stack.pop();
}

void SortareTopologica :: Read ()
{
    f >> N >> M;

    for(int x, y, i = 1; i <= M; ++i)   {
        f >> x >> y;
        V[x].push_back(y);
    }
}

void SortareTopologica :: DF(int nod)
{
    Viz[nod] = 1;

    for(std :: vector < int > :: iterator it = V[nod].begin(); it != V[nod].end(); ++it)
        if(!Viz[*it])    DF(*it);

    my_stack.push(nod);
}

void SortareTopologica :: TopologicSort()
{
    for(int i = 1; i <= N; ++i)
        if(!Viz[i]) DF(i);
}

void SortareTopologica :: Write()
{
    while(!my_stack.empty())    {
        g << my_stack.top() << ' ';
        my_stack.pop();
    }

    g << '\n';
}

int main()
{
    SortareTopologica obj;

    obj.Read();
    obj.TopologicSort();
    obj.Write();

    return 0;
}