Cod sursa(job #1536853)

Utilizator ArambasaVlad Arambasa Arambasa Data 26 noiembrie 2015 18:44:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int NMax = 50000;
vector <int> G[NMax + 5];
int Use[NMax + 5];
int O[NMax + 5];
int N,M,k;

void Read()
{
    fin>>N>>M;
    for(int i = 1; i<=N; i++)
        {
            int x,y;
            fin>>x>>y;
            G[x].push_back(y);
        }

}

void DFS(int Nod)
{
    Use[Nod] = 1;
    // Zona 1
    for(int i = 0; i < (int)G[Nod].size(); i++)
        {
            int Vecin = G[Nod][i];
            if(!Use[Vecin])
               {
                    // Zona 2
                    DFS(Vecin);
                    // Zona 3
               }

        }
    //Zona 4
    O[++k] = Nod;
}

void Print()
{
    for(int i = k; i>=1; i--)
        fout<<O[i]<<" ";
    fout<<"\n";
}

int main()
{
    Read();
    for(int i = 1; i<=N; i++)
        if(!Use[i])
            DFS(i);
    Print();
    return 0;
}