Cod sursa(job #1502974)

Utilizator jimcarterJim Carter jimcarter Data 15 octombrie 2015 12:51:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#include <vector>
using namespace std;

FILE *f = fopen ( "sortaret.in" , "r" ) , *g = fopen ( "sortaret.out" , "w" );

const int MAX = 50001;
int N , M , i , v1 , v2;
bool visited [ MAX ];
vector <int> edge[MAX] , topsort;

void read()
{
    fscanf ( f , "%d %d" , &N , &M );
    for ( i = 1 ; i <= M ; i ++ )
    {
        fscanf ( f , "%d %d" , &v1 , &v2 );
        edge[v1].push_back (v2);
    }
}

void dfs ( int node )
{
    visited [ node ] = true;
    for ( int i = 0 ; i < edge [ node ] . size() ; i ++ )
        if ( visited [ edge [ node ] [ i ] ] == false )
            dfs ( edge [ node ] [ i ] );
    topsort.push_back ( node );
}

void print()
{
    for ( i = topsort.size() - 1 ; i >= 0 ; i -- )
        fprintf ( g , "%d " , topsort [ i ] );
    fprintf ( g , "\n" );
}

int main()
{
    read();

    //solve
    for ( i = 1 ; i <= N ; i ++ )
        if ( visited [ i ] == false )
            dfs ( i );

    print();
    return 0;
}