Cod sursa(job #1603526)

Utilizator xtreme77Patrick Sava xtreme77 Data 17 februarie 2016 17:15:08
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 14 ;

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

vector < int > gr [ MAX ] ;

vector < int > sol ;

bitset < MAX > viz ;

inline void dfs ( int nod )
{
    viz [ nod ] = 1 ;
    for ( auto x : gr [ nod ] )
        if ( viz [ x ] == 0 )
            dfs ( x ) ;
    sol.push_back( nod ) ;
}

int main()
{
    int n , m ;
    fin >> n >> m ;
    for ( ; -- m ; )
    {
        int x , y ;
        fin >> x >> y ;
        gr [ x ].push_back ( y ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i )
        if ( !viz [ i ] )
            dfs ( i ) ;
    reverse ( sol.begin() , sol.end() ) ;
    for ( auto x : sol )
        fout << x << ' ' ;
    return 0;
}