Cod sursa(job #3146050)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 18 august 2023 12:44:11
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <fstream>
#include <vector>
#include <algorithm>
//_I_AM_THE_ULTIMATE_FLOPPER//
using namespace std;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
long long fact [ 200005 ];
long long gcd ( long long x, long long y )
{
    long long a = x ;
    long long b = y ;

    while ( b != 0 )
    {
        long long r = a % b ;
        a = b;
        b = r ;
    }

    return a ;
}
long long mod = 1e9+7;
long long a[ 200005 ] ;
long long b [ 200005 ];
long long v[ 200005 ];
long long n, m, q ;
long long bin_pow(long long a, long long b )
{
    long long prd = 1;
    while ( b )
    {
        if ( b % 2 == 1 )
            prd = ( prd * a ) % mod ;

        a = ( a * a ) % mod ;
        b /= 2;
    }

    return prd ;
}

long long inv( long long a, long long mod )
{
    return ( bin_pow( a, mod - 2 )) ;
}


void dfs(int k , vector<int> adj [] , vector<int>& topsort , vector<int>& color)
{
    for ( int i = 0 ; i < adj [ k ] .size() ; i ++)
    {
        if ( color [ adj [ k ] [ i ] ] == 0 )
        {
            color [ adj [ k ][ i ]] = 1;
            dfs ( adj [  k] [ i ] , adj ,topsort , color );
        }

    }

    topsort.push_back(k );

}
void solve()
{
    long long n , m ;
    cin >> n >> m ;

    vector<int> adj [ n + 1] ;
    vector<int> color ( n + 1) ;
    vector<int> topsort;

    for ( int i = 1; i <= n; i ++ )
        color [ i ] =0 ;
    for ( int i = 1; i <= m ; i ++ )
    {
        long long a, b;
        cin >> a >> b;
        adj [ a ] .push_back(b);
    }

    vector<int> topsport ;

    for ( int i = 1 ; i <= n ; i ++ )
    {
        if ( color [ i ] == 0 )
        {
            color [ i ] = 1;
            dfs ( i , adj , topsort ,color );

        }
    }

    reverse(topsort.begin(),topsort.end());

    for ( int i = 0 ; i < topsort.size(); i ++)
        cout << topsort [ i ] << " ";




}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);;
    int test = 1 ;

    while ( test -- )
        solve();
    return 0;
}