Cod sursa(job #1294026)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 16 decembrie 2014 21:41:43
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream is("sortaret.in");
ofstream os("sortaret.out");

#define DIM 50001

int N, M, x, y;
bool Vis[DIM];

vector <int> G[DIM];
vector <int> finTime;
void DF(int x);

int main()
{
    is >> N >> M;
    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y;
        G[x].push_back(y);
    }

    for ( int i = 1; i <= N; ++i )
        if ( !Vis[i] )
            DF(i);

    for ( int i = N-1; i >= 0; --i )
        os << finTime[i] << " ";


    is.close();
    os.close();
}

void DF(int x)
{
    Vis[x] = true;

    for ( int i = 0; i < G[x].size(); ++i )
    {
        if ( !Vis[G[x][i]] )
            DF(G[x][i]);
    }

    finTime.push_back(x);
}