Cod sursa(job #1985500)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 27 mai 2017 23:57:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

#define pb push_back
#define ll long long

using namespace std;

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

const int NLIM = 50000 + 10;

int N, M;
vector< int > graph[NLIM];
stack< int > res;
int dfs[NLIM];


void f( int nod )
{
    for( int j = 0; j < graph[nod].size(); ++j )
    {
        int nnod = graph[nod][j];
        if( !dfs[nnod] )
        {
            f( nnod );
        }
    }

    dfs[nod] = 1;
    res.push( nod );
}

int main()
{
    fin >> N >> M;
    for( int i = 0; i < M; ++i )
    {
        int x, y;
        fin >> x >> y;
        graph[x].pb( y );
    }

    for( int i = 1; i <= N; ++i )
    {
        if( !dfs[i] )
        {
            f( i );
        }
    }

    while( res.size() )
    {
        fout << res.top() << " ";
        res.pop();
    }

    return 0;
}